The merge-sort algorithm for sorting a list is based on dividing the list, then sorting the smaller lists (using a recursive call to merge-sort) and finally merging these sorted smaller lists. Accordingly, to sort a list L: 

- divide L into two lists L1 and L2, of approximately equal length; 

- sort L1 and L2 giving S1 and S2; and 

- merge S1 and S2 giving L3 (sorted). Write a Prolog implementation of merge-sort. 

Test results: 

?- merge_sort([83,5,5,4,16,6], M). M = [4, 5, 5, 6, 16, 83] 

?- merge_sort([3,2,5,4,1,6], M). M = [1,2,3,4,5,6]