*Key*- A non-negative integer or a list of positive integers.
*Order*- One of the atoms =<, >=, < or >.
*List1*- List.
*List2*- List.
*List3*- List or variable.

If List1 and List2 are not lists of compound terms, use Key = 0.

If List1 and List2 are lists of compound terms, then the sort will be according to the Keyth argument of the lists' elements. If Key = 0, then the sort is on the entire terms.

For two lists [e1,e2,e3] and [f1,f2,f3], e1 is compared to f1. The resulting element (dictated by Key, Order and the standard ordering below, with ties being resolved in favour of the element from List1) is put into List3, and the process continued with the remaining input lists. This process continues until both lists are exhausted.

In particular, this will merge two sorted lists into a sorted list. The merge is stable, i.e. the order of elements with the same key is preserved. If List1 and List2 contain elements with identical keys, List1's elements will occur first in List3.

In all cases where List1 and List2 are sorted, Order specifies whether the lists are sorted into ascending (<, =<) or descending (>, >=) order and whether duplicates are to be retained (=<, >=) or eliminated (<, >). The way to remember the Order argument is that it is the relation which holds between adjacent elements in the result.

The sort is done according to the standard ordering of terms. See compare/3 for the definition of this standard ordering. Note in particular that numbers are first ordered by their type (integer, float, etc) and only then by their magnitude, i.e. sorting numbers of different types may not give the expected result.

- merge(+, +, +, +, -) is det

*(5) type error*- Key is greater than 0, and one of List1 and List2 does not have all elements compound terms.
*(5) type error*- Key is not an integer or a list of integers.
*(6) out of range*- One of the compound terms in List1 or List2 has not got as many as Key arguments.

Success: merge(0,<,[2,4,6],[1,3,5],L). (gives L=[1,2,3,4,5,6]). merge(0,<,[f(1),f(7)],[f(8),f(10)],L). (gives L=[f(1),f(7),f(8),f(10)]). merge(0,<,[f(2),f(1)],[f(3),f(8)],L). (gives L=[f(2),f(1),f(3),f(8)]). merge(0,<,[f(2)],[f(6),f(1)],L). (gives L=[f(2),f(6),f(1)]). merge(0,>,[1,e,q],[Q,2,a],L). (gives Q=_g60,L=[_g60,1,2,a,e,q]). merge(0,>,[f(8),f(6)],[f(4),f(1)],L). (gives L=[f(8),f(6),f(4),f(1)]). merge(2,<,[f(2,1),f(6,4)],[f(6,3),f(8,6)],L). (gives L=[f(2,1),f(6,3),f(6,4),f(8,6)]). merge(2,<,[q(2,1),f(6,4)],[a(6,3),i(8,6)],L). (gives L=[q(2,1),a(6,3),f(6,4),i(8,6)]). merge(2,<,[f(a,b),f(c,a)],[f(k,a)],L). (gives L=[f(k,a),f(a,b),f(c,a)). merge(0,=<,[1,2],[3,4,4,5],L). (gives L=[1,2,3,4,4,5]). merge([2,1], =<, [f(1,a(1)), f(0,a(3))], [f(3,a(2)), f(1,a(4))], L). (gives L=[f(1,a(1)), f(3,a(2)), f(0,a(3)), f(1,a(4))]). Fail: merge(0,<,[2,4,6],[1,3,5],[1,2,3,4,5]). Error: merge(1,<,[f(1,2),f],[f(3,4),h(1,2)],L). (Error 5). merge(0.0,<,[f(1)],[f(2)],L). (Error 5). merge(2,<,[f(1,2)],[f(8)],L). (Error 6).