sortLL1 := proc(L::listlist(nonnegint))
local B,X,n,x,j;
    B := max(map(op,L)[])+1;
    n := nops(L[1]);
    X := [seq(B^(n-j), j=1..n)];
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `

The variable B is assigned one more than the largest integer in L, the listlist of integers. The variable X is assigned the list [B,B,...,B,1], which is dot multiplied (using the undocumented builtin procedure, inner) with each sublist in L to compute the key. Because B is larger than the largest integer in L, the computed key is guaranteed to be injective and monotonic. SORT_W_ATTR does the actual sorting. It uses the technique of sorting with attributes, which is fast because it does not need to compute the inverse of the scalar. SORT_W_ATTR is a macro, not a Maple procedure. As such, it can only be used in code that is processed by tty maple (cmaple). Maple macros are limited, but occasionally useful for simplifying the source code. See the help page ?preprocessor for details. Here is the definition of SORT_W_ATTR.

$define SORT_W_ATTR(k,x,e,F) \
map(attributes, sort([seq(setattribute(k,x),e)],F))

map(attributes, sort([seq(setattribute(Float(inner(X,x)),x),x=L)],`

While this method is impressively fast, it has a practical problem. As B and n (the length of the sublists) increase, the time required to compute the scalar product increase. Theoretically one would expect this to be O(B m log m), where m is the number of sublists in L.

Can we do better? My first thought was to improve the vector, X, used in the dot product. Using powers of B for all the components is too conservative. Here is a modified approach that uses the maximum value in each column (think of L as a matrix) to form the base for each component in X.

sortLL2 := proc(L::listlist(nonnegint))
local M,n,B,X,C,k,x;
    M := map(lst -> max(op(lst)), `kernel/transpose`(L));
    n := nops(M);
    B := rtable(1..n);
    C := 0;
    for k from n to 1 by -1 do
        B[k] := C + 1;
        C := M[k]*B[k] + C;
    end do;
    X := [seq(B[k], k=1..n)];
    SORT_W_ATTR(Float(inner(X,x)), x, x=L, `

While it takes longer to compute this X, that is only done once, so the resulting speed-up in the scalar products for large lists can be significant. Alas, for uniformly distributed random integers, the effect is miniscule.

After reflecting on this during my daily walk, I came up with a simpler way to compute an appropriate key, using string catenation rather than arithmetic. The following example shows how a listlist of positive integers is converted to a corresponding list of strings.

[  [  3, 400,   2 ] → "103" "1400" "1002" → "10314001002"
 , [ 20,  31, 203 ] → "120" "1031" "1203" → "12010311203"
 , [  0,  12,  12 ] → "100" "1012" "1012" → "10010121012"
]

sortLL3 := proc(L::listlist(nonnegint))
local X,x,n,i;
    X := map(x -> 10^length(max(op(x))), `kernel/transpose`(L));
    n := nops(X);
    SORT_W_ATTR(cat("", seq(X[i]+x[i], i=1..n)), x, x=L, 'lexorder');
end proc:

sortLL4 := proc(L::listlist(nonnegint))
local X,x;
    X := seq(10^length(max(op(x))), x = `kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

sortLL5 := proc(L::listlist(integer))
local X,x;
    X := seq(2*10^length(max((-min,max)(op(x)))), x = `kernel/transpose`(L));
    SORT_W_ATTR(cat("", X+x[]), x, x=L, 'lexorder');
end proc:

sortLL4([[3,4],[1,2]]);
                        [[1,2],[3,4]]
attributes("1112");
                        [1,2]

If two threads called sortLL5 concurrently, a string attributed by one thread could be changed by the other. The call to map(attributes, . ) would then insert a sublist from one thread into the output of the other.

Currently, very few Maple routines use threads, and not all the existing code is thread-safe. However, in the future, as multicore devices become popular, I expect that thread-safety will be important.

The Threads package provides mutexes, which can prevent collisions in data structures however, in this case, because strings are inherently global, there is no robust way to use mutex's to avoid collisions. To avoid the thread-safety issue, attributes must not be applied to strings. There is, fortunately, a solution to the thread-safety issue: enclose each string in a list and apply the attribute to the list. The Maple sort procedure can use a builtin comparator, lexorder[n], for comparing lists of strings. The index to lexorder specifies the element in the list to compare. Here is the thread-safe code:

sortLL6 := proc(L::listlist(integer))
local X,x;
    X := seq(2*10^length(max((-min,max)(op(x)))), x = `kernel/transpose`(L));
    SORT_W_ATTR([cat("", X+x[])], x, x=L, 'lexorder'[1]);
end proc:

Here are plots comparing the time and memory usage of each routine. Integers are uniformly distributed from 1 to max.

Fix n=5 (number of integers in each list)
    max=10^5
Vary m from 10 to 10^3

Fix m=100 (number of sublists)
    max=10^5
Vary n from 1 to 100

Fix m=100 (number of sublists)
    n=5   (number of integers in each list)
Vary max from 10 to 10^4

These plots were created using the Tine package. Here is the Maple Code used to assign and measure the procedures described here.