# Multiple-Key Sorting

Given a list of indices and zero or more lists of integers, output the lists of integers, sorted in ascending order, with the key priority from the first input.

## Example

Let the keys input be [1, 0, 2], and the lists input be [[5, 3, 4], [6, 2, 1], [5, 2, 1]]. Those lists need to be sorted by their second element, then first element, then third element, in ascending order:

1. First, we sort by the values at index 1: [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
2. Next, we break any ties from the first sort using the values at index 0: [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
3. Finally, we break any remaining ties with the vlues at index 2 (this doesn't actually change anything, because there are no ties remaining).

## Details

• Sorting is stable: if two elements compare equal with respect to the given sort keys, they must remain in the same relative order in the output. For example, if A and B are equal under the given sort keys, and the input was [..., A, ..., B, ...], A must be placed before B in the output.
• A sort key will never reference a non-existant element in one of the input lists.
• No sort key will be repeated. Thus, [1, 2, 1] is not a valid list of sort keys.
• Any elements not referenced by the sort keys do not factor into the sorting order. Only the initial relative order and the values of the elements referenced by the sort keys determine the output order.
• You may choose whether the sort keys are zero-indexed or one-indexed.
• There will be no negative values in the sort keys. If you choose to use one-indexing, there will be no zeroes in the sort keys either.
• Integer values will not exceed your language's natively-representable range. If your chosen language is natively capable of arbitrary-precision integers (like Python), then any integer value can be present in the input, subject to memory constraints.

## Reference Implementation (Python 2)

#!/usr/bin/env python

keys = input()
lists = input()

print sorted(lists, key=lambda l:[l[x] for x in keys])

Try it online

## Test Cases

Format: keys lists -> output. All sort keys are zero-indexed.

[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]]
[1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]]
[0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]]
[1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]]
[0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]]
[2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]]
[2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]]
[2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]]
[1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]]
[8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]]
• Some of the test cases seem obnoxiously long. Sep 29, 2016 at 12:59
• @Fatalize They're meant to cover cases where there are few sort keys compared to the lengths of the lists, and cases where there are many sort keys.
– user45941
Sep 29, 2016 at 13:00
• @Fatalize That's why we have copy and paste. If necessary, use Retina to change the format to something you can use. Sep 29, 2016 at 14:03
• Can we assume all rows will have the same length if that's the natural data type in our language (i.e. a matrix)? Sep 29, 2016 at 16:02
• @LuisMendo No. You must be able to support jagged arrays.
– user45941
Sep 29, 2016 at 16:03

# Jelly, 4 bytes

⁴ị$Þ Try it online! • Have you got a breakdown of how that works? Sep 29, 2016 at 21:41 • @JamEngulfer: It should have been specified in the answer, but: Þ is "sort with specified sort key", ⁴ị uses the second command-line argument to reorder the array (producing a sort key which works like the question asks), and$ overrides the precedence so that the program parses correctly.
– user62131
May 8, 2017 at 15:38
• -1 byte Feb 11, 2021 at 17:17

}fX

# Ruby, 35 bytes

->k,a{a.sort_by{|e|e.values_at *k}}

See it on eval.in: https://eval.in/652574

import Data.List
sortOn.flip(map.(!!))

Usage example: ( sortOn.flip(map.(!!)) ) [2,1] [[9,2,-2,-10,-6], [3,-4,-2]] -> [[3,-4,-2],[9,2,-2,-10,-6]].

Non-pointfree: f k v=sortOn(\x->map(\y->x!!y)k)v.

## Mathematica, 22 19 bytes

SortBy[Extract/@#]&

Uses 1-based indices. This unnamed function is curried, so the calling convention is:

SortBy[Extract/@#]&[{2, 1, 3}][{{5, 3, 4}, {6, 2, 1}, {5, 2, 1}}]

Mathematica's SortBy can take a list of functions in which case the individual functions are used as successive tie-breakers, so that's just what we want. All we need to do is create a list of functions which return the corresponding list element. This can be done with Extract. Extract is normally a binary function Extract[list, index] which returns a list element. However if used unarily, then Extract[index] returns a function which retrieves the element at index from a list passed to it. In other words, the index parameter of Extract can be curried. We make use of this by mapping Extract over the list of indices we're given, which creates the list of functions we need.

• Shouldn't Extract/@# be Extract/@(#+1)? The index of the input starts at 0. Sep 29, 2016 at 14:09
• @JHM "You may choose whether the sort keys are zero-indexed or one-indexed." Sep 29, 2016 at 14:10
• I stand corrected. Sep 29, 2016 at 14:14
• (Unsprisingly) elegant! But given that you're 1-indexing, shouldn't [{1, 0, 2}] be [{2, 1, 3}] in your example? Indeed, currently it seems to be sorting by first element, then head, then second element. Sep 29, 2016 at 16:31
• @GregMartin sorry, copy/paste fail. Sep 29, 2016 at 16:32

## Python, 50 bytes

lambda l,k:sorted(l,key=lambda x:[x[y]for y in k])

This is a trivially-golfed version of the reference implementation. l is the lists parameter, and k is the sort keys parameter. l can be any iterable, so long as its elements are subscriptable by integers (like lists, tuples, or int-keyed dicts). k can be any iterable.

# Brachylog, 29 bytes

tT,?hg:Tz:{:2f}o:ta
heI,?t:Im

Try it online!

### Explanation

We use the fact that o - Order can be used with an additionnal predicate as input: we order the lists by using for each [Keys, a list] the list of the elements of a list which are at index a key in the order that they appear in Keys.

Input = [Keys, List of lists]

tT,                       Call the Keys T
?hg:T                  Create the list [[T], List of lists]
z                 Zip [T] with the list of lists
:{   }o          Order by the output of this predicate
:ta       Keep only the last element of each sublist in the Output

:2f            Find all outputs of the predicate below

heI,                      Take a key I
?t:Im                 Output is the Ith element of the sublist

## CJam (12 bytes)

{{1$\f=}$\;}

}$\; e# Pop the orders to leave just sorted-values } # J, 6 bytes ]/:{&> Keys are zero-indexed. The LHS is the list of keys and the RHS is an array of values. Since J doesn't support ragged arrays, each array must be boxed. ## Usage f =: ]/:{&> < 1 0 2 ┌─────┐ │1 0 2│ └─────┘ 5 3 4 ; 6 2 1 ; 5 2 1 ┌─────┬─────┬─────┐ │5 3 4│6 2 1│5 2 1│ └─────┴─────┴─────┘ (< 1 0 2) f 5 3 4 ; 6 2 1 ; 5 2 1 ┌─────┬─────┬─────┐ │5 2 1│6 2 1│5 3 4│ └─────┴─────┴─────┘ (< 1 2) f 5 3 4 ; 6 2 1 ; 5 2 1 ┌─────┬─────┬─────┐ │6 2 1│5 2 1│5 3 4│ └─────┴─────┴─────┘ (< 0) f 4 ; 10 11 _88 ; _2 7 ┌────┬─┬─────────┐ │_2 7│4│10 11 _88│ └────┴─┴─────────┘ ## Explanation ]/:{&> Input: keys (LHS), values (RHS) {&> Select from values at each index in keys ] Get the values /: Sort up the values using the ones selected with the keys ## JavaScript (ES6), 55 bytes (k,l)=>k.reduceRight((l,i)=>l.sort((a,b)=>a[i]-b[i]),l) The ECMAscript standard doesn't guarantee that the underlying sort is stable, so the following 68-byte code doesn't make that assumption: (k,l)=>l.sort(g=(a,b,i=0)=>i<k.length?a[k[i]]-b[k[i]]||g(a,b,i+1):0) # Pyth, 5 4 bytes @LDF Try it online: Demonstration or Test Suite Thanks to @Maltysen for one byte. # Explanation: @LDFQ Q (=input) added implicitly. D sort a list of lists by @L the sublists generated by some indices FQ executes ^ with the the input as parameter I was really surprised that this worked. It's a really strange syntax. • I think you can save by replacing QE by F Sep 29, 2016 at 19:48 • @Maltysen Thanks. I thought that was only possible with a regular one-token method. Sep 29, 2016 at 19:56 • the rules for sugar are very adhoc and inconsistent, the best is unfortunately just to try out if a particular thing works. Sep 29, 2016 at 19:59 # JavaScript (ES6) 46 k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v) At each comparison during the sort, scan the key indices to find the right order Test f=k=>l=>l.sort((a,b)=>k.some(i=>v=a[i]-b[i])&&v) ;[1, 0, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[5, 2, 1], [6, 2, 1], [5, 3, 4]] [1, 2] [[5, 3, 4], [6, 2, 1], [5, 2, 1]] -> [[6, 2, 1], [5, 2, 1], [5, 3, 4]] [0, 1] [[1, 2], [2, 1]] -> [[1, 2], [2, 1]] [1, 0] [[1, 2], [2, 1]] -> [[2, 1], [1, 2]] [0] [[4], [10, 11, -88], [-2, 7]] -> [[-2, 7], [4], [10, 11, -88]] [2] [[-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6]] -> [[-9, 8, -5, -1, -7, -8, -5, -6, 5, -6, 6], [-7, 6, 2, -8, -7, 7, -3, 3, 0, -6, 1], [-1, -5, 8, -1, -4, -10, -5, 4, 4, 6, -8, 4, 2]] [2, 1] [[9, 2, -2, -10, -6], [3, -4, -2]] -> [[3, -4, -2], [9, 2, -2, -10, -6]] [2, 4, 8] [[5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5], [-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3]] -> [[-7, -8, -6, 7, 3, 8, 6, -7, -2, 0, -6, -4, 4, -3, 2, -3], [5, -3, 4, -6, -1, -2, -2, -4, 5], [-2, -3, 6, -4, -1, -4, -4, -5, 8, 9, 9, -3, 3, -9, -3], [2, 0, 10, -10, -1, 2, -1, 5, -1, 10, -5]] [1, 2, 3, 4, 5] [[-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [5, 3, -6, -5, -4, -4, -8, 2], [9, -4, 1, -1, -3, -2], [-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [1, -5, -3, -10, -7, 9, -8, -5, -1], [-9, 4, -1, -1, 2, 4]] -> [[-6, -10, 4, -10, 6, 6, -1, 3, 0, 0], [1, -5, -3, -10, -7, 9, -8, -5, -1], [9, -4, 1, -1, -3, -2], [1, -2, -7, -6, -7, -7, -1, 0, -4, 3, 3], [-9, -1, -7, -9, -10, -2, -8, -10, -10, -3], [7, -1, -7, 2, -2, 9, 7, 5, -6, -8], [-7, 3, -8, 3, 5, -1, 6, -6, 9, 8], [5, 3, -6, -5, -4, -4, -8, 2], [-9, 4, -1, -1, 2, 4]] [8, 7, 3, 2, 4, 9, 1] [[8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9]] -> [[10, -1, 3, 0, -4, 1, -5, -4, -1, -7, 9, -9, -1, -5, 7, 8, 9, 6, -3], [5, 6, -9, 0, -1, 5, 4, 7, 5, 10, 2, 5, 7, -9], [0, -9, -7, -2, 2, -5, 7, 4, 6, -4, 1, 8, -7, 10], [4, -8, 6, -10, -2, -3, 2, -6, 9, 5, 4, 10, 2, 3], [8, -5, 1, -6, -1, -4, 6, 10, 10, 6, 9, 5]] .split('\n').map(row=>{ var [keys,list,expected]=row.split(/] -?>? ?\[/) keys=eval(keys+']'); list=eval('['+list+']'); expected=eval('['+expected); var result=f(keys)(list); var ok=result.join|==expected.join|; console.log(ok?'OK':'KO',keys+' '+list.join|+' -> ' +expected.join|,ok?'':result.join|) }) # Perl 6 23 20 19 bytes ->\a,\b{b.sort:{.[|a]}} {$^a;$^b.sort:{.[|$a]}}
{$^b.sort: *.[|$^a]}
{$^b.sort: *[|$^a]}

## PHP, 212 170 bytes

function m(&$i,$k){foreach($i as$a=>$y)for($b=-1;++$b<$a;){for($p=0;$p<count($k)&!$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x];);if($r>0){$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;}}} PHP has no stable sort built in anymore; picking an older version there is no way to do a recursive callback with the required specification. But nevermind: using the recursive callback iterator would cost tons; so I didn´t even check if that could do it. The inner loop could be replaced with another foreach; that would save some bytes on the swapping. But without a check for$b<$a (or$b<count($i)), that will result in an infinite loop. And with that check, The foreach costs as much as the swapping wins. I first did the comparison recursively; but iteration saves tons of bytes: breakdown // bubble sort function m(&$i,$k) { foreach($i as$a=>$y)
for($b=-1;++$b<$a;) { // comparison: for($p=0;$p<count($k)                       // loop through keys
&
!$r=$i[$b][$x=$k[$p++]]-$i[$b+1][$x] // while element equals its successor ;); // if element is larger than its successor, swap them if($r>0)
{
$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;
}
}
}
• Your whole if($r>0){$s=$i[$b+1];$i[$b+1]=$i[$b];$i[$b]=$s;} can be written as$r>0&&$i[$b+1]^=$i[$b]^=$i[$b+1]^=$i[$b];, saving you 7 bytes. This uses a XOR swap with abuse of short-circuit evaluation to emulate an if(){ ... }. The swap is only executed if and only if $r>0. This uses the same trick that is (sometimes) used with databases. Often, you will see mysqli_connect( ... ) or die('Cannot connect');. Oct 2, 2016 at 15:23 • @IsmaelMiguel XOR swap does not work for arrays. And it would save 10 bytes, because I could make it the post-condition of the$b loop. ;) Oct 3, 2016 at 11:01
• I tested the XOR swap and it worked (I didn't test with the rest of the code). I wrote 2 test cases: sandbox.onlinephpfunctions.com/code/… (you code) and sandbox.onlinephpfunctions.com/code/… (XOR swap). According to text-compare.com, the output is identical. Oct 3, 2016 at 11:22
• @IsmaelMiguel To test the function You should execute it: insert m($i,$k); before the var_dump and Your version will produce garbage. Oct 3, 2016 at 12:47
• :/ I didnt even noticed that I didn't execute the function... :/ But it was a cool idea! Oct 3, 2016 at 12:58

## R 40 bytes

for(i in rev(il)){dd=dd[order(dd[,i]),]}

Explanation:

List of lists is best represented as a data.frame in R:

ll2 = list(c(5,3,4), c(5,3,7), c(6,2,1), c(6,1,3), c(5,2,1))
dd = data.frame(do.call(rbind, ll2))
dd
X1 X2 X3
1  5  3  4
2  5  3  7
3  6  2  1
4  6  1  3
5  5  2  1

If index list is il (indexing is from 1):

il = list(1, 2, 3)

Sorting can be done with following code:

for(i in rev(il)){dd = dd[order(dd[,i]),]}

Output:

dd
X1 X2 X3
5  5  2  1
1  5  3  4
2  5  3  7
4  6  1  3
3  6  2  1

## Racket 218 bytes

(λ(il ll)(define qsl(λ(l i)(if(null? l)l(let*((h(first l))(t(rest l))(g(λ(ff)(filter(λ(x)(ff(list-ref x i)
(list-ref h i)))t))))(append(qsl(g <)i)(list h)(qsl(g >=)i))))))(for((i(reverse il)))(set! ll(qsl ll i)))ll)

Ungolfed (il=index list; ll=list of lists; qsl= quicksort for list of lists; h=head (first element); t=tail (rest or remaining elements); g=modifiable filter fn):

(define qsl
(λ(l i)
(if (null? l)
l
(let* ((h (first l))
(t (rest  l))
(g (λ(ff) (filter (λ(x) (ff (list-ref x i) (list-ref h i))) t))))
(append (qsl (g <) i)
(list h)
(qsl (g >=) i)
)))))
(define f
(λ(il ll)
(for ((i (reverse il)))
(set! ll (qsl ll i)))
ll))

Testing:

(f (list 0 1 2) (list (list 5 3 4) (list 5 3 7) (list 6 2 1) (list 6 1 3) (list 5 2 1)))
(f [list 1 2] [list [list 5 3 4] [list 6 2 1] [list 5 2 3]])

Output:

'((5 2 1) (5 3 4) (5 3 7) (6 1 3) (6 2 1))
'((6 2 1) (5 2 3) (5 3 4))

# PHP, 139 Bytes

use the new spaceship operator and usort

<?$a=$_GET[a];function c($x,$y,$i=0){$k=$_GET[k];return$x[$k[$i]]-$y[$k[$i]]?:($k[++$i]?c($x,$y,$i):0);}usort($a,c);echo json_encode($a);

Instead of $x[$k[$i]]<=>$y[$k[$i]] you can use $x[$k[$i]]-$y[$k[$i]] under a PHP Version greater 7 - 2 Bytes

version with create an own index 197 Bytes like in a real library

<?$m=min(array_map(min,$a=$_GET[a]));foreach($a as$p=>$v){$k="";foreach($s=$_GET[s]as$f){$k.=str_pad($v[$f]-$m,5,0,0);}$k.=str_pad($p,5,0,0);$r[$k]=$v;}ksort($r);echo json_encode(array_values($r)); • You can try to use <?function c($x,$y,$i=0){$k=$_GET[k];return $x[$k[$i]]<=>$y[$k[$i]]?:($k[++$i]?c($x,$y,$i):0);}usort($a=$_GET[a],c);echo json_encode($a);. $_GET is a superglobal: it means that it is already a global everywhere. Remove the global$k;, move the assignment inside the function and you're done. Also, since this is using $_GET, you have to use <?. With this, you save 10 bytes. It will (hopefully) work. Oct 2, 2016 at 10:36 • @IsmaelMiguel I feel like an idiot that I'd not seen that I use the global only inside the function. Oct 2, 2016 at 13:40 • PHP sort functions use quicksort; that´s not stable. Apart from that, you can save two bytes with - instead of <=> and two with an anonyomous callback for usort. Oct 2, 2016 at 14:08 • @Titus An anonymous function can't be used because of c($x,$y,$i) at the end of the body of the function. Oct 2, 2016 at 14:13
• @JörgHülsermann Don't worry, we all make silly mistakes. Oct 2, 2016 at 14:14

# K (ngn/k), 10 bytes

{y@<y[;x]}

Try it online!

Clojure, 29 bytes

#(sort-by(fn[c](mapv c %))%2)

Nicely sort-by is stable and knows how to sort vectors, and vectors can operate as functions. ([4 6 9 7] 2) is 9 (0-based indexing).