The R13B03 release.OTP_R13B03

1 files changed, 2462 insertions, 0 deletions

diff --git a/lib/stdlib/src/lists.erl b/lib/stdlib/src/lists.erl
new file mode 100644
index 0000000000..e1f8d1c200
--- /dev/null
+++ b/lib/stdlib/src/lists.erl
@@ -0,0 +1,2462 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 1996-2009. All Rights Reserved.
+%% 
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%% 
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%% 
+%% %CopyrightEnd%
+%%
+-module(lists).
+
+-export([append/2, append/1, subtract/2, reverse/1,
+	 nth/2, nthtail/2, prefix/2, suffix/2, last/1, 
+	 seq/2, seq/3, sum/1, duplicate/2, min/1, max/1, sublist/2, sublist/3,
+	 delete/2,
+	 unzip/1, unzip3/1, zip/2, zip3/3, zipwith/3, zipwith3/4,
+	 sort/1, merge/1, merge/2, rmerge/2, merge3/3, rmerge3/3,
+	 usort/1, umerge/1, umerge3/3, umerge/2, rumerge3/3, rumerge/2,
+	 concat/1, flatten/1, flatten/2, flat_length/1, flatlength/1,
+	 keydelete/3, keyreplace/4, keytake/3, keystore/4,
+	 keysort/2, keymerge/3, rkeymerge/3, rukeymerge/3, 
+	 ukeysort/2, ukeymerge/3, keymap/3]).
+
+%% Bifs: member/2, reverse/2
+%% Bifs: keymember/3, keysearch/3, keyfind/3
+
+-export([merge/3, rmerge/3, sort/2, umerge/3, rumerge/3, usort/2]).
+
+-export([all/2,any/2,map/2,flatmap/2,foldl/3,foldr/3,filter/2,
+	 partition/2,zf/2,
+	 mapfoldl/3,mapfoldr/3,foreach/2,takewhile/2,dropwhile/2,splitwith/2,
+	 split/2]).
+
+-deprecated([flat_length/1]).
+
+%% member(X, L) -> (true | false)
+%%  test if X is a member of the list L
+%%  Now a BIF!
+
+%member(X, [X|_]) -> true;
+%member(X, [_|Y]) ->
+%	member(X, Y);
+%member(X, []) -> false.
+
+%% append(X, Y) appends lists X and Y
+
+-spec append([T], [T]) -> [T].
+
+append(L1, L2) -> L1 ++ L2.
+
+%% append(L) appends the list of lists L
+
+-spec append([[T]]) -> [T].
+
+append([E]) -> E;
+append([H|T]) -> H ++ append(T);
+append([]) -> [].
+
+%% subtract(List1, List2) subtract elements in List2 form List1.
+
+-spec subtract([T], [T]) -> [T].
+
+subtract(L1, L2) -> L1 -- L2.
+
+%% reverse(L) reverse all elements in the list L. Is now a BIF!
+
+-spec reverse([T]) -> [T].
+
+reverse([] = L) ->
+    L;
+reverse([_] = L) ->
+    L;
+reverse([A, B]) ->
+    [B, A];
+reverse([A, B | L]) ->
+    lists:reverse(L, [B, A]).
+
+%reverse([H|T], Y) ->
+%    reverse(T, [H|Y]);
+%reverse([], X) -> X.
+
+
+%% nth(N, L) returns the N`th element of the list L
+%% nthtail(N, L) returns the N`th tail of the list L
+
+-spec nth(pos_integer(), [T,...]) -> T.
+
+nth(1, [H|_]) -> H;
+nth(N, [_|T]) when N > 1 ->
+    nth(N - 1, T).
+
+-spec nthtail(non_neg_integer(), [T,...]) -> [T].
+
+nthtail(1, [_|T]) -> T;
+nthtail(N, [_|T]) when N > 1 ->
+    nthtail(N - 1, T);
+nthtail(0, L) when is_list(L) -> L.
+
+%% prefix(Prefix, List) -> (true | false)
+
+-spec prefix([T], [T]) -> boolean().
+
+prefix([X|PreTail], [X|Tail]) ->
+    prefix(PreTail, Tail);
+prefix([], List) when is_list(List) -> true;
+prefix([_|_], List) when is_list(List) -> false.
+
+%% suffix(Suffix, List) -> (true | false)
+
+-spec suffix([T], [T]) -> boolean().
+
+suffix(Suffix, List) ->
+    Delta = length(List) - length(Suffix),
+    Delta >= 0 andalso nthtail(Delta, List) =:= Suffix.
+
+%% last(List) returns the last element in a list.
+
+-spec last([T,...]) -> T.
+
+last([E|Es]) -> last(E, Es).
+
+last(_, [E|Es]) -> last(E, Es);
+last(E, []) -> E.
+
+%% seq(Min, Max) -> [Min,Min+1, ..., Max]
+%% seq(Min, Max, Incr) -> [Min,Min+Incr, ..., Max]
+%%  returns the sequence Min..Max
+%%  Min <= Max and Min and Max must be integers
+
+-spec seq(integer(), integer()) -> [integer()].
+
+seq(First, Last)
+    when is_integer(First), is_integer(Last), First-1 =< Last -> 
+    seq_loop(Last-First+1, Last, []).
+
+seq_loop(N, X, L) when N >= 4 ->
+     seq_loop(N-4, X-4, [X-3,X-2,X-1,X|L]);
+seq_loop(N, X, L) when N >= 2 ->
+     seq_loop(N-2, X-2, [X-1,X|L]);
+seq_loop(1, X, L) ->
+     [X|L];
+seq_loop(0, _, L) ->
+     L.
+
+-spec seq(integer(), integer(), integer()) -> [integer()].
+
+seq(First, Last, Inc) 
+    when is_integer(First), is_integer(Last), is_integer(Inc) -> 
+    if
+        Inc > 0, First - Inc =< Last;
+        Inc < 0, First - Inc >= Last ->
+            N = (Last - First + Inc) div Inc,
+            seq_loop(N, Inc*(N-1)+First, Inc, []);
+        Inc =:= 0, First =:= Last ->
+            seq_loop(1, First, Inc, [])
+    end.
+
+seq_loop(N, X, D, L) when N >= 4 ->
+     Y = X-D, Z = Y-D, W = Z-D,
+     seq_loop(N-4, W-D, D, [W,Z,Y,X|L]);
+seq_loop(N, X, D, L) when N >= 2 ->
+     Y = X-D,
+     seq_loop(N-2, Y-D, D, [Y,X|L]);
+seq_loop(1, X, _, L) ->
+     [X|L];
+seq_loop(0, _, _, L) ->
+     L.
+
+%% sum(L) returns the sum of the elements in L
+
+-spec sum([number()]) -> number().
+
+sum(L)          -> sum(L, 0).
+
+sum([H|T], Sum) -> sum(T, Sum + H);
+sum([], Sum)    -> Sum.
+
+%% duplicate(N, X) -> [X,X,X,.....,X]  (N times)
+%%   return N copies of X
+
+-spec duplicate(non_neg_integer(), T) -> [T].
+
+duplicate(N, X) when is_integer(N), N >= 0 -> duplicate(N, X, []).
+
+duplicate(0, _, L) -> L;
+duplicate(N, X, L) -> duplicate(N-1, X, [X|L]).
+
+%% min(L) -> returns the minimum element of the list L
+
+-spec min([T,...]) -> T.
+
+min([H|T]) -> min(T, H).
+
+min([H|T], Min) when H < Min -> min(T, H);
+min([_|T], Min)              -> min(T, Min);
+min([],    Min)              -> Min. 
+
+%% max(L) -> returns the maximum element of the list L
+
+-spec max([T,...]) -> T.
+
+max([H|T]) -> max(T, H).
+
+max([H|T], Max) when H > Max -> max(T, H);
+max([_|T], Max)              -> max(T, Max);
+max([],    Max)              -> Max.
+
+%% sublist(List, Start, Length)
+%%  Returns the sub-list starting at Start of length Length.
+
+-spec sublist([T], pos_integer(), non_neg_integer()) -> [T].
+
+sublist(List, S, L) when is_integer(L), L >= 0 ->
+    sublist(nthtail(S-1, List), L).
+
+-spec sublist([T], non_neg_integer()) -> [T].
+
+sublist(List, L) when is_integer(L), is_list(List) ->
+    sublist_2(List, L).
+
+sublist_2([H|T], L) when L > 0 ->
+    [H|sublist_2(T, L-1)];
+sublist_2(_, 0) ->
+    [];
+sublist_2(List, L) when is_list(List), L > 0 ->
+    [].
+
+%% delete(Item, List) -> List'
+%%  Delete the first occurrence of Item from the list L.
+
+-spec delete(T, [T]) -> [T].
+
+delete(Item, [Item|Rest]) -> Rest;
+delete(Item, [H|Rest]) -> 
+    [H|delete(Item, Rest)];
+delete(_, []) -> [].
+
+%% Return [{X0, Y0}, {X1, Y1}, ..., {Xn, Yn}] for lists [X0, X1, ...,
+%% Xn] and [Y0, Y1, ..., Yn].
+
+-spec zip([A], [B]) -> [{A, B}].
+
+zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)];
+zip([], []) -> [].
+
+%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn]}, for a list [{X0, Y0},
+%% {X1, Y1}, ..., {Xn, Yn}].
+
+-spec unzip([{A, B}]) -> {[A], [B]}.
+
+unzip(Ts) -> unzip(Ts, [], []).
+
+unzip([{X, Y} | Ts], Xs, Ys) -> unzip(Ts, [X | Xs], [Y | Ys]);
+unzip([], Xs, Ys) -> {reverse(Xs), reverse(Ys)}.
+
+%% Return [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}] for lists [X0,
+%% X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn].
+
+-spec zip3([A], [B], [C]) -> [{A, B, C}].
+
+zip3([X | Xs], [Y | Ys], [Z | Zs]) -> [{X, Y, Z} | zip3(Xs, Ys, Zs)];
+zip3([], [], []) -> [].
+
+%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn], [Z0, Z1, ..., Zn]}, for
+%% a list [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}].
+
+-spec unzip3([{A, B, C}]) -> {[A], [B], [C]}.
+
+unzip3(Ts) -> unzip3(Ts, [], [], []).
+
+unzip3([{X, Y, Z} | Ts], Xs, Ys, Zs) ->
+    unzip3(Ts, [X | Xs], [Y | Ys], [Z | Zs]);
+unzip3([], Xs, Ys, Zs) ->
+    {reverse(Xs), reverse(Ys), reverse(Zs)}.
+
+%% Return [F(X0, Y0), F(X1, Y1), ..., F(Xn, Yn)] for lists [X0, X1, ...,
+%% Xn] and [Y0, Y1, ..., Yn].
+
+-spec zipwith(fun((X, Y) -> R), [X], [Y]) -> [R].
+
+zipwith(F, [X | Xs], [Y | Ys]) -> [F(X, Y) | zipwith(F, Xs, Ys)];
+zipwith(F, [], []) when is_function(F, 2) -> [].
+
+%% Return [F(X0, Y0, Z0), F(X1, Y1, Z1), ..., F(Xn, Yn, Zn)] for lists
+%% [X0, X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn].
+
+-spec zipwith3(fun((X, Y, Z) -> R), [X], [Y], [Z]) -> [R].
+
+zipwith3(F, [X | Xs], [Y | Ys], [Z | Zs]) ->
+    [F(X, Y, Z) | zipwith3(F, Xs, Ys, Zs)];
+zipwith3(F, [], [], []) when is_function(F, 3) -> [].
+
+%% sort(List) -> L
+%%  sorts the list L
+
+-spec sort([T]) -> [T].
+
+sort([X, Y | L] = L0) when X =< Y ->
+    case L of
+	[] -> 
+	    L0;
+	[Z] when Y =< Z ->
+	    L0;
+	[Z] when X =< Z ->
+	    [X, Z, Y];
+	[Z] ->
+	    [Z, X, Y];
+	_ when X == Y ->
+	    sort_1(Y, L, [X]);
+	_ ->
+	    split_1(X, Y, L, [], [])
+    end;
+sort([X, Y | L]) ->
+    case L of
+	[] ->
+	    [Y, X];
+	[Z] when X =< Z ->
+	    [Y, X | L];
+	[Z] when Y =< Z ->
+	    [Y, Z, X];
+	[Z] ->
+	    [Z, Y, X];
+	_ ->
+	    split_2(X, Y, L, [], [])
+    end;
+sort([_] = L) ->
+    L;
+sort([] = L) ->
+    L.
+
+sort_1(X, [Y | L], R) when X == Y ->
+    sort_1(Y, L, [X | R]);
+sort_1(X, [Y | L], R) when X < Y ->
+    split_1(X, Y, L, R, []);
+sort_1(X, [Y | L], R) ->
+    split_2(X, Y, L, R, []);
+sort_1(X, [], R) ->
+    lists:reverse(R, [X]).
+
+%% merge(List) -> L
+%%  merges a list of sorted lists
+
+-spec merge([T]) -> [T].
+
+merge(L) ->
+    mergel(L, []).
+
+%% merge3(X, Y, Z) -> L
+%%  merges three sorted lists X, Y and Z
+
+-spec merge3([_], [_], [_]) -> [_].
+
+merge3(L1, [], L3) ->
+   merge(L1, L3);
+merge3(L1, L2, []) ->
+   merge(L1, L2);
+merge3(L1, [H2 | T2], [H3 | T3]) ->
+   lists:reverse(merge3_1(L1, [], H2, T2, H3, T3), []).
+
+%% rmerge3(X, Y, Z) -> L
+%%  merges three reversed sorted lists X, Y and Z
+
+-spec rmerge3([_], [_], [_]) -> [_].
+
+rmerge3(L1, [], L3) ->
+   rmerge(L1, L3);
+rmerge3(L1, L2, []) ->
+   rmerge(L1, L2);
+rmerge3(L1, [H2 | T2], [H3 | T3]) ->
+   lists:reverse(rmerge3_1(L1, [], H2, T2, H3, T3), []).
+
+%% merge(X, Y) -> L
+%%  merges two sorted lists X and Y
+
+-spec merge([_], [_]) -> [_].
+
+merge(T1, []) ->
+    T1;
+merge(T1, [H2 | T2]) ->
+    lists:reverse(merge2_1(T1, H2, T2, []), []).
+
+%% rmerge(X, Y) -> L
+%%  merges two reversed sorted lists X and Y
+
+%% reverse(rmerge(reverse(A),reverse(B))) is equal to merge(I,A,B).
+
+-spec rmerge([_], [_]) -> [_].
+
+rmerge(T1, []) ->
+    T1;
+rmerge(T1, [H2 | T2]) ->
+    lists:reverse(rmerge2_1(T1, H2, T2, []), []).
+
+%% concat(L) concatenate the list representation of the elements
+%%  in L - the elements in L can be atoms, numbers of strings.
+%%  Returns a list of characters.
+
+-type concat_thing() :: atom() | integer() | float() | string().
+-spec concat([concat_thing()]) -> string().
+
+concat(List) ->
+    flatmap(fun thing_to_list/1, List).
+
+thing_to_list(X) when is_integer(X) -> integer_to_list(X);
+thing_to_list(X) when is_float(X)   -> float_to_list(X);
+thing_to_list(X) when is_atom(X)    -> atom_to_list(X);
+thing_to_list(X) when is_list(X)    -> X.	%Assumed to be a string
+
+%% flatten(List)
+%% flatten(List, Tail)
+%%  Flatten a list, adding optional tail.
+
+-spec flatten([_]) -> [_].
+
+flatten(List) when is_list(List) ->
+    do_flatten(List, []).
+
+-spec flatten([_], [_]) -> [_].
+
+flatten(List, Tail) when is_list(List), is_list(Tail) ->
+    do_flatten(List, Tail).
+
+do_flatten([H|T], Tail) when is_list(H) ->
+    do_flatten(H, do_flatten(T, Tail));
+do_flatten([H|T], Tail) ->
+    [H|do_flatten(T, Tail)];
+do_flatten([], Tail) ->
+    Tail.
+
+%% flat_length(List) (undocumented can be removed later)
+%%  Calculate the length of a list of lists.
+
+-spec flat_length([_]) -> non_neg_integer().
+
+flat_length(List) -> flatlength(List).
+
+%% flatlength(List)
+%%  Calculate the length of a list of lists.
+
+-spec flatlength([_]) -> non_neg_integer().
+
+flatlength(List) ->
+    flatlength(List, 0).
+
+flatlength([H|T], L) when is_list(H) ->
+    flatlength(H, flatlength(T, L));
+flatlength([_|T], L) ->
+    flatlength(T, L + 1);
+flatlength([], L) -> L.
+
+%% keymember(Key, Index, [Tuple]) Now a BIF!
+%% keysearch(Key, Index, [Tuple]) Now a BIF!
+%% keydelete(Key, Index, [Tuple])
+%% keyreplace(Key, Index, [Tuple], NewTuple)
+%% keytake(Key, Index, [Tuple])
+%% keystore(Key, Index, [Tuple], NewTuple)
+%% keysort(Index, [Tuple])
+%% keymerge(Index, [Tuple], [Tuple])
+%% ukeysort(Index, [Tuple])
+%% ukeymerge(Index, [Tuple], [Tuple])
+%% keymap(Function, Index, [Tuple])
+%% keymap(Function, ExtraArgs, Index, [Tuple])
+
+%keymember(K,N,L) when is_integer(N), N > 0 ->
+%    keymember3(K,N,L).
+
+%keymember3(Key, N, [T|Ts]) when element(N, T) == Key -> true;
+%keymember3(Key, N, [T|Ts]) ->
+%    keymember3(Key, N, Ts);
+%keymember3(Key, N, []) -> false.
+
+%keysearch(K, N, L) when is_integer(N), N > 0 ->
+%    keysearch3(K, N, L).
+
+%keysearch3(Key, N, [H|T]) when element(N, H) == Key ->
+%    {value, H};
+%keysearch3(Key, N, [H|T]) ->
+%    keysearch3(Key, N, T);
+%keysearch3(Key, N, []) -> false.
+
+-spec keydelete(_, pos_integer(), [T]) -> [T].
+
+keydelete(K, N, L) when is_integer(N), N > 0 ->
+    keydelete3(K, N, L).
+
+keydelete3(Key, N, [H|T]) when element(N, H) == Key -> T;
+keydelete3(Key, N, [H|T]) ->
+    [H|keydelete3(Key, N, T)];
+keydelete3(_, _, []) -> [].
+
+-spec keyreplace(_, pos_integer(), [_], tuple()) -> [_].
+
+keyreplace(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) ->
+    keyreplace3(K, N, L, New).
+
+keyreplace3(Key, Pos, [Tup|Tail], New) when element(Pos, Tup) == Key ->
+    [New|Tail];
+keyreplace3(Key, Pos, [H|T], New) ->
+    [H|keyreplace3(Key, Pos, T, New)];
+keyreplace3(_, _, [], _) -> [].
+
+-spec keytake(_, pos_integer(), [_]) -> {'value', tuple(), [_]} | 'false'.
+
+keytake(Key, N, L) when is_integer(N), N > 0 ->
+    keytake(Key, N, L, []).
+
+keytake(Key, N, [H|T], L) when element(N, H) == Key ->
+    {value, H, lists:reverse(L, T)};
+keytake(Key, N, [H|T], L) ->
+    keytake(Key, N, T, [H|L]);
+keytake(_K, _N, [], _L) -> false.
+
+-spec keystore(_, pos_integer(), [_], tuple()) -> [_].
+keystore(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) ->
+    keystore2(K, N, L, New).
+
+keystore2(Key, N, [H|T], New) when element(N, H) == Key ->
+    [New|T];
+keystore2(Key, N, [H|T], New) ->
+    [H|keystore2(Key, N, T, New)];
+keystore2(_Key, _N, [], New) ->
+    [New].
+
+-spec keysort(pos_integer(), [T]) -> [T] when is_subtype(T, tuple()).
+
+keysort(I, L) when is_integer(I), I > 0 ->
+    case L of
+	[] -> L;
+	[_] -> L;
+	[X, Y | T] ->
+	    case {element(I, X), element(I, Y)} of
+		{EX, EY} when EX =< EY ->
+		    case T of
+			[] ->
+			    L;
+			[Z] ->
+			    case element(I, Z) of
+				EZ when EY =< EZ ->
+				    L;
+				EZ when EX =< EZ ->
+				    [X, Z, Y];
+				_EZ ->
+				    [Z, X, Y]
+			    end;
+			_ when X == Y ->
+			    keysort_1(I, Y, EY, T, [X]);
+			_ ->
+			    keysplit_1(I, X, EX, Y, EY, T, [], [])
+		    end;
+		{EX, EY} ->
+		    case T of
+			[] ->
+			    [Y, X];
+			[Z] ->
+			    case element(I, Z) of
+				EZ when EX =< EZ ->
+				    [Y, X | T];
+				EZ when EY =< EZ ->
+				    [Y, Z, X];
+				_EZ ->
+				    [Z, Y, X]
+			    end;
+			_ ->
+			    keysplit_2(I, X, EX, Y, EY, T, [], [])
+		    end
+	    end
+    end.
+
+keysort_1(I, X, EX, [Y | L], R) when X == Y ->
+    keysort_1(I, Y, EX, L, [X | R]);
+keysort_1(I, X, EX, [Y | L], R) ->
+    case element(I, Y) of
+	EY when EX =< EY ->
+	    keysplit_1(I, X, EX, Y, EY, L, R, []);
+	EY ->
+	    keysplit_2(I, X, EX, Y, EY, L, R, [])
+    end;
+keysort_1(_I, X, _EX, [], R) ->
+    lists:reverse(R, [X]).
+
+-spec keymerge(pos_integer(), [X], [Y]) ->
+	     [R] when is_subtype(X, tuple()), is_subtype(Y, tuple()), is_subtype(R, tuple()).
+
+keymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> 
+    case L2 of
+	[] ->
+	    T1;
+	[H2 | T2] ->
+	    E2 = element(Index, H2),
+	    M = keymerge2_1(Index, T1, E2, H2, T2, []),
+	    lists:reverse(M, [])
+    end.
+
+%% reverse(rkeymerge(I,reverse(A),reverse(B))) is equal to keymerge(I,A,B).
+
+-spec rkeymerge(pos_integer(), [X], [Y]) ->
+	     [R] when is_subtype(X, tuple()), is_subtype(Y, tuple()), is_subtype(R, tuple()).
+
+rkeymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> 
+    case L2 of
+	[] ->
+	    T1;
+	[H2 | T2] ->
+	    E2 = element(Index, H2),
+	    M = rkeymerge2_1(Index, T1, E2, H2, T2, []),
+	    lists:reverse(M, [])
+    end.
+
+-spec ukeysort(pos_integer(), [T]) -> [T] when is_subtype(T, tuple()).
+
+ukeysort(I, L) when is_integer(I), I > 0 ->
+    case L of
+	[] -> L;
+	[_] -> L;
+	[X, Y | T] ->
+            case {element(I, X), element(I, Y)} of
+                {EX, EY} when EX == EY ->
+                    ukeysort_1(I, X, EX, T);
+                {EX, EY} when EX < EY ->
+                    case T of
+                        [] ->
+                            L;
+                        [Z] ->
+                            case element(I, Z) of
+                                EZ when EY == EZ ->
+                                    [X, Y];
+                                EZ when EY < EZ ->
+                                    [X, Y, Z];
+                                EZ when EZ == EX ->
+                                    [X, Y];
+                                EZ when EX =< EZ ->
+                                    [X, Z, Y];
+                                _EZ ->
+                                    [Z, X, Y]
+                            end;
+                        _ ->
+                            ukeysplit_1(I, X, EX, Y, EY, T, [], [])
+                    end;
+                {EX, EY} ->
+                    case T of
+                        [] ->
+                            [Y, X];
+                        [Z] ->
+                            case element(I, Z) of
+                                EZ when EX == EZ ->
+                                    [Y, X];
+                                EZ when EX < EZ ->
+                                    [Y, X, Z];
+                                EZ when EY == EZ ->
+                                    [Y, X];
+                                EZ when EY =< EZ ->
+                                    [Y, Z, X];
+                                _EZ ->
+                                    [Z, Y, X]
+                            end;
+                        _ ->
+			    ukeysplit_2(I, Y, EY, T, [X])
+                    end
+	    end
+    end.
+
+ukeysort_1(I, X, EX, [Y | L]) ->
+    case element(I, Y) of
+        EY when EX == EY ->
+            ukeysort_1(I, X, EX, L);
+	EY when EX < EY ->
+	    ukeysplit_1(I, X, EX, Y, EY, L, [], []);
+	EY ->
+	    ukeysplit_2(I, Y, EY, L, [X])
+    end;
+ukeysort_1(_I, X, _EX, []) ->
+    [X].
+
+-spec ukeymerge(pos_integer(), [X], [Y]) ->
+	     [(X | Y)] when is_subtype(X, tuple()), is_subtype(Y, tuple()).
+
+ukeymerge(Index, L1, T2) when is_integer(Index), Index > 0 ->
+    case L1 of
+	[] ->
+	    T2;
+	[H1 | T1] ->
+	    E1 = element(Index, H1),
+	    M = ukeymerge2_2(Index, T1, E1, H1, T2, []),
+	    lists:reverse(M, [])
+    end.
+
+%% reverse(rukeymerge(I,reverse(A),reverse(B))) is equal to ukeymerge(I,A,B).
+
+-spec rukeymerge(pos_integer(), [X], [Y]) ->
+	     [(X | Y)] when is_subtype(X, tuple()), is_subtype(Y, tuple()).
+
+rukeymerge(Index, T1, L2) when is_integer(Index), Index > 0 ->
+    case L2 of
+	[] ->
+	    T1;
+	[H2 | T2] ->
+	    E2 = element(Index, H2),
+	    M = rukeymerge2_1(Index, T1, E2, T2, [], H2),
+	    lists:reverse(M, [])
+    end.
+
+-spec keymap(fun((_) -> _), pos_integer(), [tuple()]) -> [tuple()].
+
+keymap(Fun, Index, [Tup|Tail]) ->
+   [setelement(Index, Tup, Fun(element(Index, Tup)))|keymap(Fun, Index, Tail)];
+keymap(Fun, Index, []) when is_integer(Index), Index >= 1, 
+                            is_function(Fun, 1) -> [].
+
+%%% Suggestion from OTP-2948: sort and merge with Fun.
+
+-spec sort(fun((T, T) -> boolean()), [T]) -> [T].
+
+sort(Fun, []) when is_function(Fun, 2) ->
+    [];
+sort(Fun, [_] = L) when is_function(Fun, 2) ->
+    L;
+sort(Fun, [X, Y | T]) ->
+    case Fun(X, Y) of
+	true ->
+	    fsplit_1(Y, X, Fun, T, [], []);
+	false ->
+	    fsplit_2(Y, X, Fun, T, [], [])
+    end.
+
+-spec merge(fun((X, Y) -> boolean()), [X], [Y]) -> [_].
+
+merge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) ->
+    lists:reverse(fmerge2_1(T1, H2, Fun, T2, []), []);
+merge(Fun, T1, []) when is_function(Fun, 2) ->
+    T1.
+
+%% reverse(rmerge(F,reverse(A),reverse(B))) is equal to merge(F,A,B).
+
+-spec rmerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_].
+
+rmerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) ->
+    lists:reverse(rfmerge2_1(T1, H2, Fun, T2, []), []);
+rmerge(Fun, T1, []) when is_function(Fun, 2) ->
+    T1.
+
+-spec usort(fun((T, T) -> boolean()), [T]) -> [T].
+
+usort(Fun, [_] = L) when is_function(Fun, 2) ->
+    L;
+usort(Fun, [] = L) when is_function(Fun, 2) ->
+    L;
+usort(Fun, [X | L]) when is_function(Fun, 2) ->
+    usort_1(Fun, X, L).
+
+usort_1(Fun, X, [Y | L]) ->
+    case Fun(X, Y) of
+        true ->
+            case Fun(Y, X) of
+                true -> % X equal to Y
+                    case L of
+                        [] ->
+                            [X];
+                        _ ->
+                            usort_1(Fun, X, L)
+                    end;
+                false ->
+                    ufsplit_1(Y, X, Fun, L, [], [])
+            end;
+        false  ->
+	    ufsplit_2(Y, L, Fun, [X])
+    end.
+                    
+-spec umerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_].
+
+umerge(Fun, [], T2) when is_function(Fun, 2) ->
+    T2;
+umerge(Fun, [H1 | T1], T2) when is_function(Fun, 2) ->
+    lists:reverse(ufmerge2_2(H1, T1, Fun, T2, []), []).
+
+%% reverse(rumerge(F,reverse(A),reverse(B))) is equal to umerge(F,A,B).
+
+-spec rumerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_].
+
+rumerge(Fun, T1, []) when is_function(Fun, 2) ->
+    T1;
+rumerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) ->
+    lists:reverse(rufmerge2_1(T1, H2, Fun, T2, []), []).
+
+%% usort(List) -> L
+%%  sorts the list L, removes duplicates
+
+-spec usort([T]) -> [T].
+
+usort([X, Y | L] = L0) when X < Y ->
+    case L of
+	[] ->
+	    L0;
+	[Z] when Y < Z ->
+	    L0;
+	[Z] when Y == Z ->
+	    [X, Y];
+	[Z] when Z < X ->
+	    [Z, X, Y];
+	[Z] when Z == X ->
+	    [X, Y];
+	[Z] ->
+	    [X, Z, Y];
+	_ ->
+	    usplit_1(X, Y, L, [], [])
+    end;
+usort([X, Y | L]) when X > Y ->
+    case L of
+	[] ->
+	    [Y, X];
+	[Z] when X < Z ->
+	    [Y, X | L];
+	[Z] when X == Z ->
+	    [Y, X];
+	[Z] when Z < Y ->
+	    [Z, Y, X];
+	[Z] when Z == Y ->
+	    [Y, X];
+	[Z] ->
+	    [Y, Z, X];
+        _ ->
+            usplit_2(X, Y, L, [], [])
+    end;
+usort([X, _Y | L]) ->
+    usort_1(X, L);
+usort([_] = L) ->
+    L;
+usort([]) ->
+    [].
+
+usort_1(X, [Y | L]) when X == Y ->
+    usort_1(X, L);
+usort_1(X, [Y | L]) when X < Y ->
+    usplit_1(X, Y, L, [], []);
+usort_1(X, [Y | L]) ->
+    usplit_2(X, Y, L, [], []);
+usort_1(X, []) ->
+    [X].
+
+%% umerge(List) -> L
+%%  merges a list of sorted lists without duplicates, removes duplicates
+
+-spec umerge([T]) -> [T].
+
+umerge(L) ->
+    umergel(L).
+
+%% umerge3(X, Y, Z) -> L
+%%  merges three sorted lists X, Y and Z without duplicates, 
+%%  removes duplicates
+
+-spec umerge3([_], [_], [_]) -> [_].
+
+umerge3(L1, [], L3) ->
+   umerge(L1, L3);
+umerge3(L1, L2, []) ->
+   umerge(L1, L2);
+umerge3(L1, [H2 | T2], [H3 | T3]) ->
+   lists:reverse(umerge3_1(L1, [H2 | H3], T2, H2, [], T3, H3), []).
+
+%% rumerge3(X, Y, Z) -> L
+%%  merges three reversed sorted lists X, Y and Z without duplicates,
+%%  removes duplicates
+
+-spec rumerge3([_], [_], [_]) -> [_].
+
+rumerge3(L1, [], L3) ->
+   rumerge(L1, L3);
+rumerge3(L1, L2, []) ->
+   rumerge(L1, L2);
+rumerge3(L1, [H2 | T2], [H3 | T3]) ->
+   lists:reverse(rumerge3_1(L1, T2, H2, [], T3, H3),[]).
+
+%% umerge(X, Y) -> L
+%%  merges two sorted lists X and Y without duplicates, removes duplicates
+
+-spec umerge([_], [_]) -> [_].
+
+umerge([], T2) ->
+    T2;
+umerge([H1 | T1], T2) ->
+    lists:reverse(umerge2_2(T1, T2, [], H1), []).
+
+%% rumerge(X, Y) -> L
+%%  merges two reversed sorted lists X and Y without duplicates,
+%%  removes duplicates
+
+%% reverse(rumerge(reverse(A),reverse(B))) is equal to umerge(I,A,B).
+
+-spec rumerge([_], [_]) -> [_].
+
+rumerge(T1, []) ->
+    T1;
+rumerge(T1, [H2 | T2]) ->
+    lists:reverse(rumerge2_1(T1, T2, [], H2), []).
+
+%% all(Predicate, List)
+%% any(Predicate, List)
+%% map(Function, List)
+%% flatmap(Function, List)
+%% foldl(Function, First, List)
+%% foldr(Function, Last, List)
+%% filter(Predicate, List)
+%% zf(Function, List)
+%% mapfoldl(Function, First, List)
+%% mapfoldr(Function, Last, List)
+%% foreach(Function, List)
+%% takewhile(Predicate, List)
+%% dropwhile(Predicate, List)
+%% splitwith(Predicate, List)
+%%  for list programming. Function here is a 'fun'. For backward compatibility,
+%%  {Module,Function} is still accepted.
+%% 
+%%  The name zf is a joke!
+%%
+%%  N.B. Unless where the functions actually needs it only foreach/2/3,
+%%  which is meant to be used for its side effects, has a defined order
+%%  of evaluation.
+%%
+%%  There are also versions with an extra argument, ExtraArgs, which is a
+%%  list of extra arguments to each call.
+
+-spec all(fun((T) -> boolean()), [T]) -> boolean().
+
+all(Pred, [Hd|Tail]) ->
+    case Pred(Hd) of
+	true -> all(Pred, Tail);
+	false -> false
+    end;
+all(Pred, []) when is_function(Pred, 1) -> true. 
+
+-spec any(fun((T) -> boolean()), [T]) -> boolean().
+
+any(Pred, [Hd|Tail]) ->
+    case Pred(Hd) of
+	true -> true;
+	false -> any(Pred, Tail)
+    end;
+any(Pred, []) when is_function(Pred, 1) -> false. 
+
+-spec map(fun((D) -> R), [D]) -> [R].
+
+map(F, [H|T]) ->
+    [F(H)|map(F, T)];
+map(F, []) when is_function(F, 1) -> [].
+
+-spec flatmap(fun((D) -> [R]), [D]) -> [R].
+
+flatmap(F, [Hd|Tail]) ->
+    F(Hd) ++ flatmap(F, Tail);
+flatmap(F, []) when is_function(F, 1) -> [].
+
+-spec foldl(fun((T, _) -> _), _, [T]) -> _.
+
+foldl(F, Accu, [Hd|Tail]) ->
+    foldl(F, F(Hd, Accu), Tail);
+foldl(F, Accu, []) when is_function(F, 2) -> Accu.
+
+-spec foldr(fun((T, _) -> _), _, [T]) -> _.
+
+foldr(F, Accu, [Hd|Tail]) ->
+    F(Hd, foldr(F, Accu, Tail));
+foldr(F, Accu, []) when is_function(F, 2) -> Accu.
+
+-spec filter(Pred :: fun((T) -> boolean()), List :: [T]) -> [T].
+
+filter(Pred, List) when is_function(Pred, 1) ->
+    [ E || E <- List, Pred(E) ].
+
+%% Equivalent to {filter(F, L), filter(NotF, L)}, if NotF = 'fun(X) ->
+%% not F(X) end'.
+
+-spec partition(Pred :: fun((T) -> boolean()), List :: [T]) -> {[T], [T]}.
+
+partition(Pred, L) ->
+    partition(Pred, L, [], []).
+
+partition(Pred, [H | T], As, Bs) ->
+    case Pred(H) of
+	true -> partition(Pred, T, [H | As], Bs);
+	false -> partition(Pred, T, As, [H | Bs])
+    end;
+partition(Pred, [], As, Bs) when is_function(Pred, 1) ->
+    {reverse(As), reverse(Bs)}.
+
+-spec zf(fun((T) -> boolean() | {'true', X}), [T]) -> [(T | X)].
+
+zf(F, [Hd|Tail]) ->
+    case F(Hd) of
+	true ->
+	    [Hd|zf(F, Tail)];
+	{true,Val} ->
+	    [Val|zf(F, Tail)];
+	false ->
+	    zf(F, Tail)
+    end;
+zf(F, []) when is_function(F, 1) -> [].
+
+-spec foreach(F :: fun((T) -> _), List :: [T]) -> 'ok'.
+
+foreach(F, [Hd|Tail]) ->
+    F(Hd),
+    foreach(F, Tail);
+foreach(F, []) when is_function(F, 1) -> ok.
+
+-spec mapfoldl(fun((T, _) -> {_, _}), _, [T]) -> {[_], _}.
+
+mapfoldl(F, Accu0, [Hd|Tail]) ->
+    {R,Accu1} = F(Hd, Accu0),
+    {Rs,Accu2} = mapfoldl(F, Accu1, Tail),
+    {[R|Rs],Accu2};
+mapfoldl(F, Accu, []) when is_function(F, 2) -> {[],Accu}.
+
+-spec mapfoldr(fun((T, _) -> {_, _}), _, [T]) -> {[_], _}.
+
+mapfoldr(F, Accu0, [Hd|Tail]) ->
+    {Rs,Accu1} = mapfoldr(F, Accu0, Tail),
+    {R,Accu2} = F(Hd, Accu1),
+    {[R|Rs],Accu2};
+mapfoldr(F, Accu, []) when is_function(F, 2) -> {[],Accu}.
+
+-spec takewhile(fun((T) -> boolean()), [T]) -> [T].
+
+takewhile(Pred, [Hd|Tail]) ->
+    case Pred(Hd) of
+	true -> [Hd|takewhile(Pred, Tail)];
+	false -> []
+    end;
+takewhile(Pred, []) when is_function(Pred, 1) -> [].
+
+-spec dropwhile(fun((T) -> boolean()), [T]) -> [T].
+
+dropwhile(Pred, [Hd|Tail]=Rest) ->
+    case Pred(Hd) of
+	true -> dropwhile(Pred, Tail);
+	false -> Rest
+    end;
+dropwhile(Pred, []) when is_function(Pred, 1) -> [].
+
+-spec splitwith(fun((T) -> boolean()), [T]) -> {[T], [T]}.
+
+splitwith(Pred, List) when is_function(Pred, 1) ->
+    splitwith(Pred, List, []).
+
+splitwith(Pred, [Hd|Tail], Taken) ->
+    case Pred(Hd) of
+	true -> splitwith(Pred, Tail, [Hd|Taken]);
+	false -> {reverse(Taken), [Hd|Tail]}
+    end;
+splitwith(Pred, [], Taken) when is_function(Pred, 1) ->
+    {reverse(Taken),[]}.
+
+-spec split(non_neg_integer(), [T]) -> {[T], [T]}.
+
+split(N, List) when is_integer(N), N >= 0, is_list(List) ->
+    case split(N, List, []) of
+	{_, _} = Result -> Result;
+	Fault when is_atom(Fault) ->
+	    erlang:error(Fault, [N,List])
+    end;
+split(N, List) ->
+    erlang:error(badarg, [N,List]).
+
+split(0, L, R) ->
+    {lists:reverse(R, []), L};
+split(N, [H|T], R) ->
+    split(N-1, T, [H|R]);
+split(_, [], _) ->
+    badarg.
+
+%%% =================================================================
+%%% Here follows the implementation of the sort functions.
+%%%
+%%% These functions used to be in their own module (lists_sort),
+%%% but have now been placed here to allow Dialyzer to produce better
+%%% type information.
+%%% =================================================================
+
+-compile({inline, 
+          [{merge3_12,7}, {merge3_21,7}, {rmerge3_12,7}, {rmerge3_21,7}]}).
+
+-compile({inline, 
+          [{umerge3_12,8}, {umerge3_21,8},
+	   {rumerge3_12a,7}, {rumerge3_12b,8}]}).
+
+-compile({inline, 
+          [{keymerge3_12,12}, {keymerge3_21,12}, 
+           {rkeymerge3_12,12}, {rkeymerge3_21,12}]}).
+
+-compile({inline,
+          [{ukeymerge3_12,13}, {ukeymerge3_21,13},
+	   {rukeymerge3_12a,11}, {rukeymerge3_21a,13},
+	   {rukeymerge3_12b,12}, {rukeymerge3_21b,12}]}).
+
+%% sort/1
+
+%% Ascending.
+split_1(X, Y, [Z | L], R, Rs) when Z >= Y ->
+    split_1(Y, Z, L, [X | R], Rs);
+split_1(X, Y, [Z | L], R, Rs) when Z >= X ->
+    split_1(Z, Y, L, [X | R], Rs);
+split_1(X, Y, [Z | L], [], Rs) ->
+    split_1(X, Y, L, [Z], Rs);
+split_1(X, Y, [Z | L], R, Rs) ->
+    split_1_1(X, Y, L, R, Rs, Z);
+split_1(X, Y, [], R, Rs) ->
+    rmergel([[Y, X | R] | Rs], []).
+
+split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= Y ->
+    split_1_1(Y, Z, L, [X | R], Rs, S);
+split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= X ->
+    split_1_1(Z, Y, L, [X | R], Rs, S);
+split_1_1(X, Y, [Z | L], R, Rs, S) when S =< Z ->
+    split_1(S, Z, L, [], [[Y, X | R] | Rs]);
+split_1_1(X, Y, [Z | L], R, Rs, S) ->
+    split_1(Z, S, L, [], [[Y, X | R] | Rs]);
+split_1_1(X, Y, [], R, Rs, S) ->
+    rmergel([[S], [Y, X | R] | Rs], []).
+
+%% Descending.
+split_2(X, Y, [Z | L], R, Rs) when Z =< Y ->
+    split_2(Y, Z, L, [X | R], Rs);
+split_2(X, Y, [Z | L], R, Rs) when Z =< X ->
+    split_2(Z, Y, L, [X | R], Rs);
+split_2(X, Y, [Z | L], [], Rs) ->
+    split_2(X, Y, L, [Z], Rs);
+split_2(X, Y, [Z | L], R, Rs) ->
+    split_2_1(X, Y, L, R, Rs, Z);
+split_2(X, Y, [], R, Rs) ->
+    mergel([[Y, X | R] | Rs], []).
+
+split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< Y ->
+    split_2_1(Y, Z, L, [X | R], Rs, S);
+split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< X ->
+    split_2_1(Z, Y, L, [X | R], Rs, S);
+split_2_1(X, Y, [Z | L], R, Rs, S) when S > Z ->
+    split_2(S, Z, L, [], [[Y, X | R] | Rs]);
+split_2_1(X, Y, [Z | L], R, Rs, S) ->
+    split_2(Z, S, L, [], [[Y, X | R] | Rs]);
+split_2_1(X, Y, [], R, Rs, S) ->
+    mergel([[S], [Y, X | R] | Rs], []).
+
+%% merge/1
+
+mergel([[] | L], Acc) ->
+    mergel(L, Acc);
+mergel([T1, [H2 | T2], [H3 | T3] | L], Acc) ->
+    mergel(L, [merge3_1(T1, [], H2, T2, H3, T3) | Acc]);
+mergel([T1, [H2 | T2]], Acc) ->
+    rmergel([merge2_1(T1, H2, T2, []) | Acc], []);
+mergel([L], []) ->
+    L;
+mergel([L], Acc) ->
+    rmergel([lists:reverse(L, []) | Acc], []);
+mergel([], []) ->
+    [];
+mergel([], Acc) ->
+    rmergel(Acc, []);
+mergel([A, [] | L], Acc) ->
+    mergel([A | L], Acc);
+mergel([A, B, [] | L], Acc) ->
+    mergel([A, B | L], Acc).
+
+rmergel([[H3 | T3], [H2 | T2], T1 | L], Acc) ->
+    rmergel(L, [rmerge3_1(T1, [], H2, T2, H3, T3) | Acc]);
+rmergel([[H2 | T2], T1], Acc) ->
+    mergel([rmerge2_1(T1, H2, T2, []) | Acc], []);
+rmergel([L], Acc) ->
+    mergel([lists:reverse(L, []) | Acc], []);
+rmergel([], Acc) ->
+    mergel(Acc, []).
+
+%% merge3/3
+
+%% Take L1 apart.
+merge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 =< H2 ->
+    merge3_12(T1, H1, H2, T2, H3, T3, M);
+merge3_1([H1 | T1], M, H2, T2, H3, T3) ->
+    merge3_21(T1, H1, H2, T2, H3, T3, M);
+merge3_1([], M, H2, T2, H3, T3) when H2 =< H3 ->
+    merge2_1(T2, H3, T3, [H2 | M]);
+merge3_1([], M, H2, T2, H3, T3) ->
+    merge2_2(T2, H3, T3, M, H2).
+
+%% Take L2 apart.
+merge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 =< H2 ->
+    merge3_12(T1, H1, H2, T2, H3, T3, M);
+merge3_2(T1, H1, M, [H2 | T2], H3, T3) ->
+    merge3_21(T1, H1, H2, T2, H3, T3, M);
+merge3_2(T1, H1, M, [], H3, T3) when H1 =< H3 ->
+    merge2_1(T1, H3, T3, [H1 | M]);
+merge3_2(T1, H1, M, [], H3, T3) ->
+    merge2_2(T1, H3, T3, M, H1).
+
+% H1 =< H2. Inlined.
+merge3_12(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 ->
+    merge3_1(T1, [H1 | M], H2, T2, H3, T3);
+merge3_12(T1, H1, H2, T2, H3, T3, M) ->
+    merge3_12_3(T1, H1, H2, T2, [H3 | M], T3).
+
+% H1 =< H2, take L3 apart.
+merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 ->
+    merge3_1(T1, [H1 | M], H2, T2, H3, T3);
+merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) ->
+    merge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
+merge3_12_3(T1, H1, H2, T2, M, []) ->
+    merge2_1(T1, H2, T2, [H1 | M]).
+
+% H1 > H2. Inlined.
+merge3_21(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 ->
+    merge3_2(T1, H1, [H2 | M], T2, H3, T3);
+merge3_21(T1, H1, H2, T2, H3, T3, M) ->
+    merge3_21_3(T1, H1, H2, T2, [H3 | M], T3).
+
+% H1 > H2, take L3 apart.
+merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 ->
+    merge3_2(T1, H1, [H2 | M], T2, H3, T3);
+merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) ->
+    merge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
+merge3_21_3(T1, H1, H2, T2, M, []) ->
+    merge2_2(T1, H2, T2, M, H1).
+
+%% rmerge/3
+
+%% Take L1 apart.
+rmerge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 =< H2 ->
+    rmerge3_12(T1, H1, H2, T2, H3, T3, M);
+rmerge3_1([H1 | T1], M, H2, T2, H3, T3) ->
+    rmerge3_21(T1, H1, H2, T2, H3, T3, M);
+rmerge3_1([], M, H2, T2, H3, T3) when H2 =< H3 ->
+    rmerge2_2(T2, H3, T3, M, H2);
+rmerge3_1([], M, H2, T2, H3, T3) ->
+    rmerge2_1(T2, H3, T3, [H2 | M]).
+
+%% Take L2 apart.
+rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 =< H2 ->
+    rmerge3_12(T1, H1, H2, T2, H3, T3, M);
+rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) ->
+    rmerge3_21(T1, H1, H2, T2, H3, T3, M);
+rmerge3_2(T1, H1, M, [], H3, T3) when H1 =< H3 ->
+    rmerge2_2(T1, H3, T3, M, H1);
+rmerge3_2(T1, H1, M, [], H3, T3) ->
+    rmerge2_1(T1, H3, T3, [H1 | M]).
+
+% H1 =< H2. Inlined.
+rmerge3_12(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 ->
+    rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
+rmerge3_12(T1, H1, H2, T2, H3, T3, M) ->
+    rmerge3_2(T1, H1, [H2 | M], T2, H3, T3).
+
+% H1 =< H2, take L3 apart.
+rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 ->
+    rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
+rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) ->
+    rmerge3_2(T1, H1, [H2 | M], T2, H3, T3);
+rmerge3_12_3(T1, H1, H2, T2, M, []) ->
+    rmerge2_2(T1, H2, T2, M, H1).
+
+% H1 > H2. Inlined.
+rmerge3_21(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 ->
+    rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
+rmerge3_21(T1, H1, H2, T2, H3, T3, M) ->
+    rmerge3_1(T1, [H1 | M], H2, T2, H3, T3).
+
+% H1 > H2, take L3 apart.
+rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 ->
+    rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
+rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) ->
+    rmerge3_1(T1, [H1 | M], H2, T2, H3, T3);
+rmerge3_21_3(T1, H1, H2, T2, M, []) ->
+    rmerge2_1(T1, H2, T2, [H1 | M]).
+
+%% merge/2
+
+merge2_1([H1 | T1], H2, T2, M) when H1 =< H2 ->
+    merge2_1(T1, H2, T2, [H1 | M]);
+merge2_1([H1 | T1], H2, T2, M) ->
+    merge2_2(T1, H2, T2, M, H1);
+merge2_1([], H2, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+merge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 ->
+    merge2_1(T1, H2, T2, [H1, HdM | M]);
+merge2_2(T1, HdM, [H2 | T2], M, H1) ->
+    merge2_2(T1, H2, T2, [HdM | M], H1);
+merge2_2(T1, HdM, [], M, H1) ->
+    lists:reverse(T1, [H1, HdM | M]).
+
+%% rmerge/2
+
+rmerge2_1([H1 | T1], H2, T2, M) when H1 =< H2 ->
+    rmerge2_2(T1, H2, T2, M, H1);
+rmerge2_1([H1 | T1], H2, T2, M) ->
+    rmerge2_1(T1, H2, T2, [H1 | M]);
+rmerge2_1([], H2, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+rmerge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 ->
+    rmerge2_2(T1, H2, T2, [HdM | M], H1);
+rmerge2_2(T1, HdM, [H2 | T2], M, H1) ->
+    rmerge2_1(T1, H2, T2, [H1, HdM | M]);
+rmerge2_2(T1, HdM, [], M, H1) ->
+    lists:reverse(T1, [H1, HdM | M]).
+
+%% usort/1
+
+%% Ascending.
+usplit_1(X, Y, [Z | L], R, Rs) when Z > Y ->
+    usplit_1(Y, Z, L, [X | R], Rs);
+usplit_1(X, Y, [Z | L], R, Rs) when Z == Y ->
+    usplit_1(X, Y, L, R, Rs);
+usplit_1(X, Y, [Z | L], R, Rs) when Z > X ->
+    usplit_1(Z, Y, L, [X | R], Rs);
+usplit_1(X, Y, [Z | L], R, Rs) when Z == X ->
+    usplit_1(X, Y, L, R, Rs);
+usplit_1(X, Y, [Z | L], [], Rs) ->
+    usplit_1(X, Y, L, [Z], Rs);
+usplit_1(X, Y, [Z | L], R, Rs) ->
+    usplit_1_1(X, Y, L, R, Rs, Z);
+usplit_1(X, Y, [], R, Rs) ->
+    rumergel([[Y, X | R] | Rs], [], asc).
+
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > Y ->
+    usplit_1_1(Y, Z, L, [X | R], Rs, S);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == Y ->
+    usplit_1_1(X, Y, L, R, Rs, S);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > X ->
+    usplit_1_1(Z, Y, L, [X | R], Rs, S);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == X ->
+    usplit_1_1(X, Y, L, R, Rs, S);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > S ->
+    usplit_1(S, Z, L, [], [[Y, X | R] | Rs]);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == S ->
+    usplit_1_1(X, Y, L, R, Rs, S);
+usplit_1_1(X, Y, [Z | L], R, Rs, S) ->
+    usplit_1(Z, S, L, [], [[Y, X | R] | Rs]);
+usplit_1_1(X, Y, [], R, Rs, S) ->
+    rumergel([[S], [Y, X | R] | Rs], [], asc).
+
+%% Descending.
+usplit_2(X, Y, [Z | L], R, Rs) when Z < Y ->
+    usplit_2(Y, Z, L, [X | R], Rs);
+usplit_2(X, Y, [Z | L], R, Rs) when Z == Y ->
+    usplit_2(X, Y, L, R, Rs);
+usplit_2(X, Y, [Z | L], R, Rs) when Z < X ->
+    usplit_2(Z, Y, L, [X | R], Rs);
+usplit_2(X, Y, [Z | L], R, Rs) when Z == X ->
+    usplit_2(X, Y, L, R, Rs);
+usplit_2(X, Y, [Z | L], [], Rs) ->
+    usplit_2(X, Y, L, [Z], Rs);
+usplit_2(X, Y, [Z | L], R, Rs) ->
+    usplit_2_1(X, Y, L, R, Rs, Z);
+usplit_2(X, Y, [], R, Rs) ->
+    umergel([[Y, X | R] | Rs], [], desc).
+
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < Y ->
+    usplit_2_1(Y, Z, L, [X | R], Rs, S);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == Y ->
+    usplit_2_1(X, Y, L, R, Rs, S);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < X ->
+    usplit_2_1(Z, Y, L, [X | R], Rs, S);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == X ->
+    usplit_2_1(X, Y, L, R, Rs, S);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < S ->
+    usplit_2(S, Z, L, [], [[Y, X | R] | Rs]);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == S ->
+    usplit_2_1(X, Y, L, R, Rs, S);
+usplit_2_1(X, Y, [Z | L], R, Rs, S) ->
+    usplit_2(Z, S, L, [], [[Y, X | R] | Rs]);
+usplit_2_1(X, Y, [], R, Rs, S) ->
+    umergel([[S], [Y, X | R] | Rs], [], desc).
+
+%% umerge/1
+
+umergel(L) ->
+    umergel(L, [], asc).
+
+umergel([[] | L], Acc, O) ->
+    umergel(L, Acc, O);
+umergel([T1, [H2 | T2], [H3 | T3] | L], Acc, asc) ->
+    umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], asc);
+umergel([[H3 | T3], [H2 | T2], T1 | L], Acc, desc) ->
+    umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], desc);
+umergel([A, [] | L], Acc, O) ->
+    umergel([A | L], Acc, O);
+umergel([A, B, [] | L], Acc, O) ->
+    umergel([A, B | L], Acc, O);
+umergel([[H1 | T1], T2 | L], Acc, asc) ->
+    umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], asc);
+umergel([T2, [H1 | T1] | L], Acc, desc) ->
+    umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], desc);
+umergel([L], [], _O) ->
+    L;
+umergel([L], Acc, O) ->
+    rumergel([lists:reverse(L, []) | Acc], [], O);
+umergel([], [], _O) ->
+    [];
+umergel([], Acc, O) ->
+    rumergel(Acc, [], O).
+
+rumergel([[H3 | T3], [H2 | T2], T1 | L], Acc, asc) ->
+    rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], asc);
+rumergel([T1, [H2 | T2], [H3 | T3] | L], Acc, desc) ->
+    rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], desc);
+rumergel([[H2 | T2], T1 | L], Acc, asc) ->
+    rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], asc);
+rumergel([T1, [H2 | T2] | L], Acc, desc) ->
+    rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], desc);
+rumergel([L], Acc, O) ->
+    umergel([lists:reverse(L, []) | Acc], [], O);
+rumergel([], Acc, O) ->
+    umergel(Acc, [], O).
+
+%% umerge3/3
+
+%% Take L1 apart.
+umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H1 =< H2 ->
+    umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM);
+umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H2 == HdM ->
+    umerge3_2(T1, H1, T2, H2, M, T3, H3);
+umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) ->
+    umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM);
+umerge3_1([], HdM, T2, H2, M, T3, H3) when H2 == HdM ->
+    umerge2_1(T2, T3, M, HdM, H3);
+umerge3_1([], _HdM, T2, H2, M, T3, H3) when H2 =< H3 ->
+    umerge2_1(T2, T3, [H2 | M], H2, H3);
+umerge3_1([], HdM, T2, H2, M, T3, H3) when H3 == HdM ->
+    umerge2_2(T2, T3, M, H2);
+umerge3_1([], _HdM, T2, H2, M, T3, H3) ->
+    umerge2_2(T2, T3, [H3 | M], H2).
+
+%% Take L2 apart.
+umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) when H1 =< H2 ->
+    umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM);
+umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) ->
+    umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM);
+umerge3_2(T1, H1, [], _HdM, M, T3, H3) when H1 =< H3 ->
+    umerge2_1(T1, T3, [H1 | M], H1, H3);
+umerge3_2(T1, H1, [], HdM, M, T3, H3) when H3 == HdM ->
+    umerge2_2(T1, T3, M, H1);
+umerge3_2(T1, H1, [], _HdM, M, T3, H3) ->
+    umerge2_2(T1, T3, [H3 | M], H1).
+
+% H1 =< H2. Inlined.
+umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) when H1 =< H3 ->
+    umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3);
+umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM ->
+    umerge3_12_3(T1, H1, T2, H2, M, T3);
+umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) ->
+    umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3).
+
+% H1 =< H2, take L3 apart.
+umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) when H1 =< H3 ->
+    umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3);
+umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) ->
+    umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3);
+umerge3_12_3(T1, H1, T2, H2, M, []) ->
+    umerge2_1(T1, T2, [H1 | M], H1, H2).
+
+% H1 > H2. Inlined.
+umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) when H2 =< H3 ->
+    umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3);
+umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM ->
+    umerge3_21_3(T1, H1, T2, H2, M, T3);
+umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) ->
+    umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3).
+
+% H1 > H2, take L3 apart.
+umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) when H2 =< H3 ->
+    umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3);
+umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) ->
+    umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3);
+umerge3_21_3(T1, H1, T2, H2, M, []) ->
+    umerge2_2(T1, T2, [H2 | M], H1).
+
+%% Take L1 apart.
+rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H2 ->
+    rumerge3_12a(T1, H1, T2, H2, M, T3, H3);
+rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H3 ->
+    rumerge3_21_3(T1, T2, H2, M, T3, H3, H1);
+rumerge3_1([H1 | T1], T2, H2, M, T3, H3) ->
+    rumerge3_1(T1, T2, H2, [H1 | M], T3, H3);
+rumerge3_1([], T2, H2, M, T3, H3) when H2 =< H3 ->
+    rumerge2_2(T2, T3, M, H3, H2);
+rumerge3_1([], T2, H2, M, T3, H3) ->
+    rumerge2_1(T2, T3, [H2 | M], H3).
+
+% H1 =< H2. Inlined.
+rumerge3_12a(T1, H1, T2, H2, M, T3, H3) when H2 =< H3 ->
+    rumerge3_12_3(T1, T2, H2, M, T3, H3, H1);
+rumerge3_12a(T1, H1, T2, H2, M, T3, H3) ->
+    rumerge3_2(T1, T2, H2, M, T3, H3, H1).
+
+%% Take L2 apart. H2M > H3. H2M > H2.
+rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H2 ->
+    % H2M > H1.
+    rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M);
+rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 == H2M ->
+    rumerge3_1(T1, T2, H2, [H1 | M], T3, H3);
+rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H3 ->
+    % H2M > H1.
+    rumerge3_21_3(T1, T2, H2, [H2M | M], T3, H3, H1);
+rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) ->
+    % H2M > H1.
+    rumerge3_1(T1, T2, H2, [H1, H2M | M], T3, H3);
+rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 == H2M ->
+    rumerge2_1(T1, T3, [H1 | M], H3);
+rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 =< H3 ->
+    rumerge2_2(T1, T3, [H2M | M], H3, H1);
+rumerge3_2(T1, [], H2M, M, T3, H3, H1) ->
+    rumerge2_1(T1, T3, [H1, H2M | M], H3).
+
+% H1 =< H2. Inlined.
+rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) when H2 =< H3 ->
+    rumerge3_12_3(T1, T2, H2, [H2M | M], T3, H3, H1);
+rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) ->
+    rumerge3_2(T1, T2, H2, [H2M | M], T3, H3, H1).
+
+% H1 =< H2, take L3 apart.
+rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 =< H3 ->
+    rumerge3_12_3(T1, T2, H2, [H3M | M], T3, H3, H1);
+rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 == H3M ->
+    rumerge3_2(T1, T2, H2, M, T3, H3, H1);
+rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) ->
+    rumerge3_2(T1, T2, H2, [H3M | M], T3, H3, H1);
+rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) when H2 == H3M ->
+    rumerge2_2(T1, T2, M, H2, H1);
+rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) ->
+    rumerge2_2(T1, T2, [H3M | M], H2, H1).
+
+% H1 > H2, take L3 apart.
+rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 =< H3 ->
+    rumerge3_21_3(T1, T2, H2, [H3M | M], T3, H3, H1);
+rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 == H3M ->
+    rumerge3_1(T1, T2, H2, [H1 | M], T3, H3);
+rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) ->
+    rumerge3_1(T1, T2, H2, [H1, H3M | M], T3, H3);
+rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) when H1 == H3M ->
+    rumerge2_1(T1, T2, [H1 | M], H2);
+rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) ->
+    rumerge2_1(T1, T2, [H1, H3M | M], H2).
+
+%% umerge/2
+
+%% Elements from the first list are kept and prioritized.
+umerge2_1([H1 | T1], T2, M, _HdM, H2) when H1 =< H2 ->
+    umerge2_1(T1, T2, [H1 | M], H1, H2);
+umerge2_1([H1 | T1], T2, M, HdM, H2) when H2 == HdM ->
+    umerge2_2(T1, T2, M, H1);
+umerge2_1([H1 | T1], T2, M, _HdM, H2) ->
+    umerge2_2(T1, T2, [H2 | M], H1);
+umerge2_1([], T2, M, HdM, H2) when H2 == HdM ->
+    lists:reverse(T2, M);
+umerge2_1([], T2, M, _HdM, H2) ->
+    lists:reverse(T2, [H2 | M]).
+
+umerge2_2(T1, [H2 | T2], M, H1) when H1 =< H2 ->
+    umerge2_1(T1, T2, [H1 | M], H1, H2);
+umerge2_2(T1, [H2 | T2], M, H1) ->
+    umerge2_2(T1, T2, [H2 | M], H1);
+umerge2_2(T1, [], M, H1) ->
+    lists:reverse(T1, [H1 | M]).
+
+%% rumerge/2
+
+%% Elements from the first list are kept and prioritized.
+rumerge2_1([H1 | T1], T2, M, H2) when H1 =< H2 ->
+    rumerge2_2(T1, T2, M, H2, H1);
+rumerge2_1([H1 | T1], T2, M, H2) ->
+    rumerge2_1(T1, T2, [H1 | M], H2);
+rumerge2_1([], T2, M, H2) ->
+    lists:reverse(T2, [H2 | M]).
+
+% H1 =< H2M.
+rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 =< H2 ->
+    rumerge2_2(T1, T2, [H2M | M], H2, H1);
+rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 == H2M ->
+    rumerge2_1(T1, T2, [H1 | M], H2);
+rumerge2_2(T1, [H2 | T2], M, H2M, H1) ->
+    rumerge2_1(T1, T2, [H1, H2M | M], H2);
+rumerge2_2(T1, [], M, H2M, H1) when H1 == H2M ->
+    lists:reverse(T1, [H1 | M]);
+rumerge2_2(T1, [], M, H2M, H1) ->
+    lists:reverse(T1, [H1, H2M | M]).
+
+%% keysort/2
+
+%% Ascending.
+keysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) ->
+    case element(I, Z) of
+	EZ when EY =< EZ ->
+            keysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs);
+        EZ when EX =< EZ ->
+            keysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs);
+        _EZ when R == [] ->
+            keysplit_1(I, X, EX, Y, EY, L, [Z], Rs);
+        EZ ->
+            keysplit_1_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L)
+    end;
+keysplit_1(I, X, _EX, Y, _EY, [], R, Rs) ->
+    rkeymergel(I, [[Y, X | R] | Rs], [], asc).
+
+keysplit_1_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) ->
+    case element(I, Z) of
+	EZ when EY =< EZ ->
+            keysplit_1_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L);
+        EZ when EX =< EZ ->
+            keysplit_1_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L);
+        EZ when ES =< EZ ->
+            keysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]);
+        EZ ->
+            keysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs])
+    end;
+keysplit_1_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) ->
+    rkeymergel(I, [[S], [Y, X | R] | Rs], [], asc).
+
+%% Descending.
+keysplit_2(I, X, EX, Y, EY, [Z | L], R, Rs) ->
+    case element(I, Z) of
+	EZ when EY > EZ ->
+            keysplit_2(I, Y, EY, Z, EZ, L, [X | R], Rs);
+        EZ when EX > EZ ->
+            keysplit_2(I, Z, EZ, Y, EY, L, [X | R], Rs);
+        _EZ when R == [] ->
+            keysplit_2(I, X, EX, Y, EY, L, [Z], Rs);
+        EZ ->
+            keysplit_2_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L)
+    end;
+keysplit_2(I, X, _EX, Y, _EY, [], R, Rs) ->
+    keymergel(I, [[Y, X | R] | Rs], [], desc).
+
+keysplit_2_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) ->
+    case element(I, Z) of
+        EZ when EY > EZ ->
+            keysplit_2_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L);
+        EZ when EX > EZ ->
+            keysplit_2_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L);
+        EZ when ES > EZ ->
+            keysplit_2(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]);
+        EZ ->
+            keysplit_2(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs])
+    end;
+keysplit_2_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) ->
+    keymergel(I, [[S], [Y, X | R] | Rs], [], desc).
+
+keymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == asc ->
+    M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3),
+    keymergel(I, L, [M | Acc], O);
+keymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == desc ->
+    M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3),
+    keymergel(I, L, [M | Acc], O);
+keymergel(I, [T1, [H2 | T2] | L], Acc, asc) ->
+    keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], asc);
+keymergel(I, [[H2 | T2], T1 | L], Acc, desc) ->
+    keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], desc);
+keymergel(_I, [L], [], _O) ->
+    L;
+keymergel(I, [L], Acc, O) ->
+    rkeymergel(I, [lists:reverse(L, []) | Acc], [], O);
+keymergel(I, [], Acc, O) ->
+    rkeymergel(I, Acc, [], O).
+
+rkeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == asc ->
+    M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3),
+    rkeymergel(I, L, [M | Acc], O);
+rkeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == desc ->
+    M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3),
+    rkeymergel(I, L, [M | Acc], O);
+rkeymergel(I, [[H2 | T2], T1 | L], Acc, asc) ->
+    rkeymergel(I, L, [rkeymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc],asc);
+rkeymergel(I, [T1, [H2 | T2] | L], Acc, desc) ->
+    rkeymergel(I, L, [rkeymerge2_1(I,T1, element(I,H2),H2,T2,[]) | Acc],desc);
+rkeymergel(I, [L], Acc, O) ->
+    keymergel(I, [lists:reverse(L, []) | Acc], [], O);
+rkeymergel(I, [], Acc, O) ->
+    keymergel(I, Acc, [], O).
+
+%%% An extra argument, D, just to avoid some move instructions.
+
+%% Take L1 apart.
+keymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D);
+        E1 ->
+            keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2)
+    end;
+keymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 ->
+    keymerge2_1(I, T2, E3, H3, T3, [H2 | M]);
+keymerge3_1(I, [], M, _D, E2, H2, T2, _E3, H3, T3) ->
+    keymerge2_2(I, T2, E2, H3, T3, M, H2).
+
+%% Take L2 apart.
+keymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1);
+        E2 ->
+            keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D)
+    end;
+keymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 ->
+    keymerge2_1(I, T1, E3, H3, T3, [H1 | M]);
+keymerge3_2(I, E1, H1, T1, [], M, _D, _E3, H3, T3) ->
+    keymerge2_2(I, T1, E1, H3, T3, M, H1).
+
+% E1 =< E2. Inlined.
+keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E1 =< E3 ->
+    keymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3);
+keymerge3_12(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) ->
+    keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]).
+
+% E1 =< E2, take L3 apart.
+keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) ->
+    case element(I, H3) of
+	E3 when E1 =< E3 ->
+            keymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3);
+        _E3 ->
+            keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M])
+    end;
+keymerge3_12_3(I, _E1, H1, T1, E2, H2, T2, [], M) ->
+    keymerge2_1(I, T1, E2, H2, T2, [H1 | M]).
+
+% E1 > E2. Inlined.
+keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E2 =< E3 ->
+    keymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3);
+keymerge3_21(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) ->
+    keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]).
+
+% E1 > E2, take L3 apart.
+keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) ->
+    case element(I, H3) of
+	E3 when E2 =< E3 ->
+            keymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3);
+        _E3 ->
+            keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M])
+    end;
+keymerge3_21_3(I, E1, H1, T1, _E2, H2, T2, [], M) ->
+    keymerge2_2(I, T1, E1, H2, T2, M, H1).
+
+%% Take L1 apart.
+rkeymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2);
+        E1 ->
+            rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D)
+    end;
+rkeymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 ->
+    rkeymerge2_2(I, E2, T2, H3, T3, M, H2);
+rkeymerge3_1(I, [], M, _D, _E2, H2, T2, E3, H3, T3) ->
+    rkeymerge2_1(I, T2, E3, H3, T3, [H2 | M]).
+
+%% Take L2 apart.
+rkeymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D);
+        E2 ->
+            rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1)
+    end;
+rkeymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 ->
+    rkeymerge2_2(I, E1, T1, H3, T3, M, H1);
+rkeymerge3_2(I, _E1, H1, T1, [], M, _D, E3, H3, T3) ->
+    rkeymerge2_1(I, T1, E3, H3, T3, [H1 | M]).
+
+% E1 =< E2. Inlined.
+rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E2 =< E3 ->
+    rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]);
+rkeymerge3_12(I, E1, H1, T1, _E2, H2, T2, E3, H3, T3, M, D) ->
+    rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3).
+
+% E1 =< E2, take L3 apart.
+rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) ->
+    case element(I, H3) of
+	E3 when E2 =< E3 ->
+            rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]);
+        E3 ->
+            rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3)
+    end;
+rkeymerge3_12_3(I, E1, H1, T1, _E2, H2, T2, [], M) ->
+    rkeymerge2_2(I, E1, T1, H2, T2, M, H1).
+
+% E1 > E2. Inlined.
+rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E1 =< E3 ->
+    rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]);
+rkeymerge3_21(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) ->
+    rkeymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3).
+
+% E1 > E2, take L3 apart.
+rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) ->
+    case element(I, H3) of
+	E3 when E1 =< E3 ->
+            rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]);
+        E3 ->
+            rkeymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3)
+    end;
+rkeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, [], M) ->
+    rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]).
+
+%% keymerge/3
+
+%% Elements from the first list are prioritized.
+keymerge2_1(I, [H1 | T1], E2, H2, T2, M) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            keymerge2_1(I, T1, E2, H2, T2, [H1 | M]);
+        E1 ->
+            keymerge2_2(I, T1, E1, H2, T2, M, H1)
+    end;
+keymerge2_1(_I, [], _E2, H2, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+keymerge2_2(I, T1, E1, HdM, [H2 | T2], M, H1) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            keymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M]);
+        _E2 ->
+            keymerge2_2(I, T1, E1, H2, T2, [HdM | M], H1)
+    end;
+keymerge2_2(_I, T1, _E1, HdM, [], M, H1) ->
+    lists:reverse(T1, [H1, HdM | M]).
+
+%% rkeymerge/3
+
+rkeymerge2_1(I, [H1 | T1], E2, H2, T2, M) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            rkeymerge2_2(I, E1, T1, H2, T2, M, H1);
+        _E1 ->
+            rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M])
+    end;
+rkeymerge2_1(_I, [], _E2, H2, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+rkeymerge2_2(I, E1, T1, HdM, [H2 | T2], M, H1) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            rkeymerge2_2(I, E1, T1, H2, T2, [HdM | M], H1);
+        E2 ->
+            rkeymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M])
+    end;
+rkeymerge2_2(_I, _E1, T1, HdM, [], M, H1) ->
+    lists:reverse(T1, [H1, HdM | M]).
+
+%% ukeysort/2
+
+%% Ascending.
+ukeysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) ->
+    case element(I, Z) of
+        EZ when EY == EZ ->
+            ukeysplit_1(I, X, EX, Y, EY, L, R, Rs);
+	EZ when EY < EZ ->
+            ukeysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs);
+        EZ when EX == EZ ->
+            ukeysplit_1(I, X, EX, Y, EY, L, R, Rs);
+        EZ when EX < EZ ->
+            ukeysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs);
+        _EZ when R == [] ->
+            ukeysplit_1(I, X, EX, Y, EY, L, [Z], Rs);
+        EZ ->
+            ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, Z, EZ)
+    end;
+ukeysplit_1(I, X, _EX, Y, _EY, [], R, Rs) ->
+    rukeymergel(I, [[Y, X | R] | Rs], []).
+
+ukeysplit_1_1(I, X, EX, Y, EY, [Z | L], R, Rs, S, ES) ->
+    case element(I, Z) of
+        EZ when EY == EZ ->
+            ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES);
+        EZ when EY < EZ ->
+            ukeysplit_1_1(I, Y, EY, Z, EZ, L, [X | R], Rs, S, ES);
+        EZ when EX == EZ ->
+            ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES);
+        EZ when EX < EZ ->
+            ukeysplit_1_1(I, Z, EZ, Y, EY, L, [X | R], Rs, S, ES);
+        EZ when ES == EZ ->
+            ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES);
+        EZ when ES < EZ ->
+            ukeysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]);
+        EZ ->
+            ukeysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs])
+    end;
+ukeysplit_1_1(I, X, _EX, Y, _EY, [], R, Rs, S, _ES) ->
+    rukeymergel(I, [[S], [Y, X | R] | Rs], []).
+
+%% Descending.
+ukeysplit_2(I, Y, EY, [Z | L], R) ->
+    case element(I, Z) of
+	EZ when EY == EZ ->
+            ukeysplit_2(I, Y, EY, L, R);
+	EZ when EY < EZ ->
+            ukeysplit_1(I, Y, EY, Z, EZ, L, [], [lists:reverse(R, [])]);
+        EZ ->
+            ukeysplit_2(I, Z, EZ, L, [Y | R])
+    end;
+ukeysplit_2(_I, Y, _EY, [], R) ->
+    [Y | R].
+
+ukeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc) ->
+    %% The fourth argument, [H2 | H3] (=HdM), may confuse type
+    %% checkers. Its purpose is to ensure that the tests H2 == HdM
+    %% and H3 == HdM in ukeymerge3_1 will always fail as long as M == [].
+    M = ukeymerge3_1(I, T1, Acc, [H2 | H3], element(I, H2), H2, T2, [],
+                     element(I, H3), H3, T3),
+    ukeymergel(I, L, [M | Acc]);
+ukeymergel(I, [[H1 | T1], T2 | L], Acc) ->
+    ukeymergel(I, L, [ukeymerge2_2(I, T1, element(I, H1), H1, T2, []) | Acc]);
+ukeymergel(_I, [L], []) ->
+    L;
+ukeymergel(I, [L], Acc) ->
+    rukeymergel(I, [lists:reverse(L, []) | Acc], []);
+ukeymergel(I, [], Acc) ->
+    rukeymergel(I, Acc, []).
+
+rukeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc) ->
+    M = rukeymerge3_1(I, T1, Acc, [], element(I, H2), H2, T2, [],
+                      element(I, H3), H3, T3),
+    rukeymergel(I, L, [M | Acc]);
+rukeymergel(I, [[H2 | T2], T1 | L], Acc) ->
+    rukeymergel(I, L, [rukeymerge2_1(I, T1, element(I,H2), T2, [], H2)|Acc]);
+rukeymergel(I, [L], Acc) ->
+    ukeymergel(I, [lists:reverse(L, []) | Acc], []);
+rukeymergel(I, [], Acc) ->
+    ukeymergel(I, Acc, []).
+
+%%% An extra argument, D, just to avoid some move instructions.
+
+%% Take L1 apart.
+ukeymerge3_1(I, [H1 | T1], D, HdM, E2, H2, T2, M, E3, H3, T3) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D);
+        E1 when E2 == HdM ->
+            ukeymerge3_2(I, E1, T1, H1, T2, HdM, T2, M, E3, H3, T3);
+        E1 ->
+            ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T2)
+    end;
+ukeymerge3_1(I, [], _D, HdM, E2, _H2, T2, M, E3, H3, T3) when E2 == HdM ->
+    ukeymerge2_1(I, T2, E3, HdM, T3, M, H3);
+ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 ->
+    ukeymerge2_1(I, T2, E3, E2, T3, [H2 | M], H3);
+ukeymerge3_1(I, [], _D, HdM, E2, H2, T2, M, E3, _H3, T3) when E3 == HdM ->
+    ukeymerge2_2(I, T2, E2, H2, T3, M);
+ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, _E3, H3, T3) ->
+    ukeymerge2_2(I, T2, E2, H2, T3, [H3 | M]).
+
+%% Take L2 apart.
+ukeymerge3_2(I, E1, T1, H1, [H2 | T2], HdM, D, M, E3, H3, T3) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T1);
+        E2 ->
+            ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D)
+    end;
+ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, E3, H3, T3) when E1 =< E3 ->
+    ukeymerge2_1(I, T1, E3, E1, T3, [H1 | M], H3);
+ukeymerge3_2(I, E1, T1, H1, [], HdM, _D, M, E3, _H3, T3) when E3 == HdM ->
+    ukeymerge2_2(I, T1, E1, H1, T3, M);
+ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, _E3, H3, T3) ->
+    ukeymerge2_2(I, T1, E1, H1, T3, [H3 | M]).
+
+% E1 =< E2. Inlined.
+ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) 
+                                                             when E1 =< E3 ->
+    ukeymerge3_1(I, T1, D, E1, E2, H2, T2, [H1 | M], E3, H3, T3);
+ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) 
+                                                             when E3 == HdM ->
+    ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, T3);
+ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) ->
+    ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3).
+
+% E1 =< E2, take L3 apart.
+ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) ->
+    case element(I, H3) of
+	E3 when E1 =< E3 ->
+            ukeymerge3_1(I, T1, T1, E1, E2, H2, T2, [H1 | M], E3, H3, T3);
+        _E3 ->
+            ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3)
+    end;
+ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, []) ->
+    ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2).
+
+% E1 > E2. Inlined.
+ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) 
+                                                             when E2 =< E3 ->
+    ukeymerge3_2(I, E1, T1, H1, T2, E2, D, [H2 | M], E3, H3, T3);
+ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) 
+                                                             when E3 == HdM ->
+    ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, T3);
+ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) ->
+    ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3).
+
+% E1 > E2, take L3 apart.
+ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) ->
+    case element(I, H3) of
+        E3 when E2 =< E3 ->
+            ukeymerge3_2(I, E1, T1, H1, T2, E2, T2, [H2 | M], E3, H3, T3);
+        _E3 ->
+            ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3)
+    end;
+ukeymerge3_21_3(I, E1, T1, H1, _E2, H2, T2, M, []) ->
+    ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]).
+
+%%% Two extra arguments, D1 and D2, just to avoid some move instructions.
+
+%% Take L1 apart.
+rukeymerge3_1(I, [H1 | T1], D1, D2, E2, H2, T2, M, E3, H3, T3) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+	    rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M);
+        E1 ->
+            rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2)
+    end;
+rukeymerge3_1(I, [], _D1, _D2, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 ->
+    rukeymerge2_2(I, T2, E2, T3, M, E3, H3, H2);
+rukeymerge3_1(I, [], _D1, _D2, _E2, H2, T2, M, E3, H3, T3) ->
+    rukeymerge2_1(I, T2, E3, T3, [H2 | M], H3).
+
+% E1 =< E2. Inlined.
+rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) when E2 =< E3 ->
+    rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3);
+rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) ->
+    rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3).
+
+% E1 > E2. Inlined
+rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D1, _D2) 
+                                                              when E1 =< E3 ->
+    rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3);
+rukeymerge3_21a(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2) ->
+    rukeymerge3_1(I, T1, D1, D2, E2, H2, T2, [H1 | M], E3, H3, T3).
+
+%% Take L2 apart. E2M > E3. E2M > E2.
+rukeymerge3_2(I, E1, H1, T1, [H2 | T2], H2M, E2M, M, E3, H3, T3) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            % E2M > E1.
+	    rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M);
+        E2 when E1 == E2M ->
+            rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3);
+        E2 ->
+            % E2M > E1.
+	    rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M)
+    end;
+rukeymerge3_2(I, E1, H1, T1, [], _H2M, E2M, M, E3, H3, T3) when E1 == E2M ->
+    rukeymerge2_1(I, T1, E3, T3, [H1 | M], H3);
+rukeymerge3_2(I, E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) when E1 =< E3 ->
+    rukeymerge2_2(I, T1, E1, T3, [H2M | M], E3, H3, H1);
+rukeymerge3_2(I, _E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) ->
+    rukeymerge2_1(I, T1, E3, T3, [H1, H2M | M], H3).
+
+% E1 =< E2. Inlined.
+rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) 
+                                                             when E2 =< E3 ->
+    rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3);
+rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) ->
+    rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H2M | M], E3, H3, T3).
+
+% E1 > E2. Inlined
+rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M,H2M) when E1 =< E3 ->
+    rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3);
+rukeymerge3_21b(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) ->
+    rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1, H2M | M], E3, H3, T3).
+
+% E1 =< E2, take L3 apart.
+rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) ->
+    case element(I, H3) of
+	E3 when E2 =< E3 ->
+            rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3);
+        E3 when E2 == E3M ->
+            rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3);
+        E3 ->
+            rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H3M | M], E3, H3, T3)
+    end;
+rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E2 == E3M ->
+    rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1);
+rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) ->
+    rukeymerge2_2(I, T1, E1, T2, [H3M | M], E2, H2, H1).
+
+% E1 > E2, take L3 apart.
+rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) ->
+    case element(I, H3) of
+	E3 when E1 =< E3 ->
+            rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3);
+        E3 when E1 == E3M ->
+            rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3);
+        E3 ->
+            rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1,H3M | M], E3, H3, T3)
+    end;
+rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E1 == E3M ->
+    rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2);
+rukeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) ->
+    rukeymerge2_1(I, T1, E2, T2, [H1, H3M | M], H2).
+
+%% ukeymerge/3
+
+%% Elements from the first list are kept and prioritized.
+ukeymerge2_1(I, [H1 | T1], E2, HdM, T2, M, H2) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2);
+        E1 when E2 == HdM ->
+            ukeymerge2_2(I, T1, E1, H1, T2, M);
+        E1 ->
+            ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M])
+    end;
+ukeymerge2_1(_I, [], E2, HdM, T2, M, _H2) when E2 == HdM ->
+    lists:reverse(T2, M);
+ukeymerge2_1(_I, [], _E2, _HdM, T2, M, H2) ->
+    lists:reverse(T2, [H2 | M]).
+
+ukeymerge2_2(I, T1, E1, H1, [H2 | T2], M) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2);
+        _E2 ->
+            ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M])
+    end;
+ukeymerge2_2(_I, T1, _E1, H1, [], M) ->
+    lists:reverse(T1, [H1 | M]).
+
+%% rukeymerge/3
+
+rukeymerge2_1(I, [H1 | T1], E2, T2, M, H2) ->
+    case element(I, H1) of
+	E1 when E1 =< E2 ->
+            rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1);
+        _E1 ->
+            rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2)
+    end;
+rukeymerge2_1(_I, [], _E2, T2, M, H2) ->
+    lists:reverse(T2, [H2 | M]).
+
+rukeymerge2_2(I, T1, E1, [H2 | T2], M, E2M, H2M, H1) ->
+    case element(I, H2) of
+	E2 when E1 =< E2 ->
+            rukeymerge2_2(I, T1, E1, T2, [H2M | M], E2, H2, H1);
+        E2 when E1 == E2M ->
+            rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2);
+        E2 ->
+            rukeymerge2_1(I, T1, E2, T2, [H1, H2M | M], H2)
+    end;
+rukeymerge2_2(_I, T1, E1, [], M, E2M, _H2M, H1) when E1 == E2M ->
+    lists:reverse(T1, [H1 | M]);
+rukeymerge2_2(_I, T1, _E1, [], M, _E2M, H2M, H1) ->
+    lists:reverse(T1, [H1, H2M | M]).
+
+%% sort/2
+
+%% Ascending.
+fsplit_1(Y, X, Fun, [Z | L], R, Rs) ->
+    case Fun(Y, Z) of
+        true -> 
+            fsplit_1(Z, Y, Fun, L, [X | R], Rs);
+        false ->
+            case Fun(X, Z) of
+                true ->
+                    fsplit_1(Y, Z, Fun, L, [X | R], Rs);
+                false when R == [] ->
+                    fsplit_1(Y, X, Fun, L, [Z], Rs);
+                false ->
+                    fsplit_1_1(Y, X, Fun, L, R, Rs, Z)
+            end
+    end;
+fsplit_1(Y, X, Fun, [], R, Rs) ->
+    rfmergel([[Y, X | R] | Rs], [], Fun, asc).
+
+fsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) ->
+    case Fun(Y, Z) of
+        true ->
+            fsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S);
+        false ->
+            case Fun(X, Z) of
+                true ->
+                    fsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S);
+                false ->
+                    case Fun(S, Z) of
+                        true ->
+                            fsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs]);
+                        false ->
+                            fsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs])
+                    end
+            end
+    end;
+fsplit_1_1(Y, X, Fun, [], R, Rs, S) ->
+    rfmergel([[S], [Y, X | R] | Rs], [], Fun, asc).
+
+%% Descending.
+fsplit_2(Y, X, Fun, [Z | L], R, Rs) ->
+    case Fun(Y, Z) of
+        false -> 
+            fsplit_2(Z, Y, Fun, L, [X | R], Rs);
+        true ->
+            case Fun(X, Z) of
+                false ->
+                    fsplit_2(Y, Z, Fun, L, [X | R], Rs);
+                true when R == [] ->
+                    fsplit_2(Y, X, Fun, L, [Z], Rs);
+                true ->
+                    fsplit_2_1(Y, X, Fun, L, R, Rs, Z)
+            end
+    end;
+fsplit_2(Y, X, Fun, [], R, Rs) ->
+    fmergel([[Y, X | R] | Rs], [], Fun, desc).
+
+fsplit_2_1(Y, X, Fun, [Z | L], R, Rs, S) ->
+    case Fun(Y, Z) of
+        false ->
+            fsplit_2_1(Z, Y, Fun, L, [X | R], Rs, S);
+        true ->
+            case Fun(X, Z) of
+                false ->
+                    fsplit_2_1(Y, Z, Fun, L, [X | R], Rs, S);
+                true ->
+                    case Fun(S, Z) of
+                        false ->
+                            fsplit_2(Z, S, Fun, L, [], [[Y, X | R] | Rs]);
+                        true ->
+                            fsplit_2(S, Z, Fun, L, [], [[Y, X | R] | Rs])
+                    end
+            end
+    end;
+fsplit_2_1(Y, X, Fun, [], R, Rs, S) ->
+    fmergel([[S], [Y, X | R] | Rs], [], Fun, desc).
+
+fmergel([T1, [H2 | T2] | L], Acc, Fun, asc) ->
+    fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc);
+fmergel([[H2 | T2], T1 | L], Acc, Fun, desc) ->
+    fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc);
+fmergel([L], [], _Fun, _O) ->
+    L;
+fmergel([L], Acc, Fun, O) ->
+    rfmergel([lists:reverse(L, []) | Acc], [], Fun, O);
+fmergel([], Acc, Fun, O) ->
+    rfmergel(Acc, [], Fun, O).
+
+rfmergel([[H2 | T2], T1 | L], Acc, Fun, asc) ->
+    rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc);
+rfmergel([T1, [H2 | T2] | L], Acc, Fun, desc) ->
+    rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc);
+rfmergel([L], Acc, Fun, O) ->
+    fmergel([lists:reverse(L, []) | Acc], [], Fun, O);
+rfmergel([], Acc, Fun, O) ->
+    fmergel(Acc, [], Fun, O).
+
+%% merge/3 
+
+%% Elements from the first list are prioritized.
+fmerge2_1([H1 | T1], H2, Fun, T2, M) ->
+    case Fun(H1, H2) of
+        true ->
+            fmerge2_1(T1, H2, Fun, T2, [H1 | M]);
+        false ->
+            fmerge2_2(H1, T1, Fun, T2, [H2 | M])
+    end;
+fmerge2_1([], H2, _Fun, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+fmerge2_2(H1, T1, Fun, [H2 | T2], M) ->
+    case Fun(H1, H2) of
+        true ->
+            fmerge2_1(T1, H2, Fun, T2, [H1 | M]);
+        false ->
+            fmerge2_2(H1, T1, Fun, T2, [H2 | M])
+    end;
+fmerge2_2(H1, T1, _Fun, [], M) ->
+    lists:reverse(T1, [H1 | M]).
+
+%% rmerge/3
+
+rfmerge2_1([H1 | T1], H2, Fun, T2, M) ->
+    case Fun(H1, H2) of
+        true ->
+            rfmerge2_2(H1, T1, Fun, T2, [H2 | M]);
+        false ->
+            rfmerge2_1(T1, H2, Fun, T2, [H1 | M])
+    end;
+rfmerge2_1([], H2, _Fun, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+rfmerge2_2(H1, T1, Fun, [H2 | T2], M) ->
+    case Fun(H1, H2) of
+        true ->
+            rfmerge2_2(H1, T1, Fun, T2, [H2 | M]);
+        false ->
+            rfmerge2_1(T1, H2, Fun, T2, [H1 | M])
+    end;
+rfmerge2_2(H1, T1, _Fun, [], M) ->
+    lists:reverse(T1, [H1 | M]).
+
+%% usort/2
+
+%% Ascending. X < Y
+ufsplit_1(Y, X, Fun, [Z | L], R, Rs) ->
+    case Fun(Y, Z) of
+        true ->
+            case Fun(Z, Y) of
+                true -> % Z equal to Y
+                    ufsplit_1(Y, X, Fun, L, R, Rs);
+                false ->
+                    ufsplit_1(Z, Y, Fun, L, [X | R], Rs)
+            end;
+        false ->
+            case Fun(X, Z) of
+                true ->
+                    case Fun(Z, X) of
+                        true -> % Z equal to X
+                            ufsplit_1(Y, X, Fun, L, R, Rs);
+                        false ->
+                            ufsplit_1(Y, Z, Fun, L, [X | R], Rs)
+                    end;
+                false when R == [] ->
+                    ufsplit_1(Y, X, Fun, L, [Z], Rs);
+                false ->
+                    ufsplit_1_1(Y, X, Fun, L, R, Rs, Z)
+            end
+    end;
+ufsplit_1(Y, X, Fun, [], R, Rs) ->
+    rufmergel([[Y, X | R] | Rs], [], Fun).
+
+%% X < Y
+ufsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) ->
+    case Fun(Y, Z) of
+        true ->
+            case Fun(Z, Y) of
+                true -> % Z equal to Y
+                    ufsplit_1_1(Y, X, Fun, L, R, Rs, S);
+                false ->
+                    ufsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S)
+            end;
+        false ->
+            case Fun(X, Z) of
+                true ->
+                    case Fun(Z, X) of
+                        true -> % Z equal to X
+                            ufsplit_1_1(Y, X, Fun, L, R, Rs, S);
+                        false ->
+                            ufsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S)
+                    end;
+                false ->
+                    case Fun(S, Z) of
+                        true ->
+                            case Fun(Z, S) of
+                                true -> % Z equal to S
+                                    ufsplit_1_1(Y, X, Fun, L, R, Rs, S);
+                                false ->
+                                    ufsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs])
+                            end;
+                        false ->
+                            ufsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs])
+                    end
+            end
+    end;
+ufsplit_1_1(Y, X, Fun, [], R, Rs, S) ->
+    rufmergel([[S], [Y, X | R] | Rs], [], Fun).
+
+%% Descending.
+ufsplit_2(Y, [Z | L], Fun, R) ->
+    case Fun(Y, Z) of
+        true ->
+            case Fun(Z, Y) of
+                true -> % Z equal to Y
+                    ufsplit_2(Y, L, Fun, R);
+                false ->
+                    ufsplit_1(Z, Y, Fun, L, [], [lists:reverse(R, [])])
+            end;
+        false ->
+            ufsplit_2(Z, L, Fun, [Y | R])
+    end;
+ufsplit_2(Y, [], _Fun, R) ->
+    [Y | R].
+
+ufmergel([[H1 | T1], T2 | L], Acc, Fun) ->
+    ufmergel(L, [ufmerge2_2(H1, T1, Fun, T2, []) | Acc], Fun);
+ufmergel([L], [], _Fun) ->
+    L;
+ufmergel([L], Acc, Fun) ->
+    rufmergel([lists:reverse(L, []) | Acc], [], Fun);
+ufmergel([], Acc, Fun) ->
+    rufmergel(Acc, [], Fun).
+
+rufmergel([[H2 | T2], T1 | L], Acc, Fun) ->
+    rufmergel(L, [rufmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun);
+rufmergel([L], Acc, Fun) ->
+    ufmergel([lists:reverse(L, []) | Acc], [], Fun);
+rufmergel([], Acc, Fun) ->
+    ufmergel(Acc, [], Fun).
+
+%% umerge/3
+
+%% Elements from the first list are kept and prioritized.
+%% HdM before H2.
+ufmerge2_1([H1 | T1], H2, Fun, T2, M, HdM) ->
+    case Fun(H1, H2) of
+        true ->
+            ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1);
+        false ->
+            case Fun(H2, HdM) of
+                true -> % HdM equal to H2
+                    ufmerge2_2(H1, T1, Fun, T2, M);
+                false ->
+                    ufmerge2_2(H1, T1, Fun, T2, [H2 | M])
+            end
+    end;
+ufmerge2_1([], H2, Fun, T2, M, HdM) ->
+    case Fun(H2, HdM) of
+        true -> % HdM equal to H2
+            lists:reverse(T2, M);
+        false ->
+            lists:reverse(T2, [H2 | M])
+    end.
+
+ufmerge2_2(H1, T1, Fun, [H2 | T2], M) ->
+    case Fun(H1, H2) of
+        true ->
+            ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1);
+        false ->
+            ufmerge2_2(H1, T1, Fun, T2, [H2 | M])
+    end;
+ufmerge2_2(H1, T1, _Fun, [], M) ->
+    lists:reverse(T1, [H1 | M]).
+
+%% rumerge/3
+
+rufmerge2_1([H1 | T1], H2, Fun, T2, M) ->
+    case Fun(H1, H2) of
+        true ->
+            rufmerge2_2(H1, T1, Fun, T2, M, H2);
+        false ->
+            rufmerge2_1(T1, H2, Fun, T2, [H1 | M])
+    end;
+rufmerge2_1([], H2, _Fun, T2, M) ->
+    lists:reverse(T2, [H2 | M]).
+
+%% H1 before H2M
+rufmerge2_2(H1, T1, Fun, [H2 | T2], M, H2M) ->
+    case Fun(H1, H2) of
+        true ->
+            rufmerge2_2(H1, T1, Fun, T2, [H2M | M], H2);
+        false ->
+            case Fun(H2M, H1) of
+                true -> % H2M equal to H1
+                    rufmerge2_1(T1, H2, Fun, T2, [H1 | M]);
+                false ->
+                    rufmerge2_1(T1, H2, Fun, T2, [H1, H2M | M])
+            end
+    end;
+rufmerge2_2(H1, T1, Fun, [], M, H2M) ->
+    case Fun(H2M, H1) of
+        true -> 
+            lists:reverse(T1, [H1 | M]);
+        false ->
+            lists:reverse(T1, [H1, H2M | M])
+    end.
+