Merging two unordered lists to a ordered list in prolog

Question

I want to write a predicate which takes 2 unsorted lists, and produces a sorted list output.

    sort_lists(List1, List2, List3) 

For example:

    [10,8,2,4,5]
    [3,7,6,9,11]

I wish to merge these into a descending sorted list, WITHOUT sorting them both beforehand and doing a simple merge. The end result would be:

    [11,10,9,8,7,6,5,4,3,2]

One idea I had was placing the numbers one at a time into the third list, each time checking the first number that was less than the current number being checked, and inserting the number in that position, but I'm struggling to implement this.. I'm quite new to prolog

Answer 1

What you describe is an application of insertion sort:

join(L1,L2,S):-
   append(L1,L2,[A|B]) -> insert_each(B,[A],S)
   ; S = [].

insert_each([],S,S).
insert_each([A|B],L,S):- 
   insert(A, ...
   insert.......

insert(A,[B|C], X):- 
   A > B -> ....
   ; ...........

You can fill in the blanks.