# How to sort list of mixed types of elements with each type a specified canonical order?

For example, here is a list

{{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"}, {3,
"d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}


The default canonical order for integer is 1,2,3,4

The default canonical order for letters is a,b,c,d,

But now I want to sort this list according to canonical integer order while "u" should be ordered before "d", how to achieve this easily?

The example list I gave here has a good structure, so can be solved with specific tricks. But the problem is general. How to sort list of mixed types of elements with each type a specified canonical order?

• I'd define a function which assigns appropriate "weights" to elements then use SortBy or KeySortBy after casting the List as an Association (which I expect is faster, but haven't verified empirically). Nov 2, 2015 at 2:39
• SortBy[list, {First, Switch[#[[2]], "u", -1, "d", 1] &}] for your particular example works. Nov 2, 2015 at 2:57
• Will your real world usage always only be "u" and "d" or will it be other letters of the alphabet? Nov 2, 2015 at 5:07
• Are you by any chance building a Wick Contraction generator? Nov 3, 2015 at 0:53
• @MikeHoneychurch other letter is possible, and even strings, they serve as labels Nov 3, 2015 at 0:57

## 5 Answers

SortBy[l, {First@#, -ToCharacterCode@Last@#} &]
(*{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4,
"u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}*)


Or the same, but slightly shorter code

SortBy[l, {#, -ToCharacterCode@#2} &@@#&]


Edit

The following uses the same sorting strategy but is much faster (by using this):

fns = {1000 # &, ToCharacterCode@# &};
l[[Ordering[Subtract @@@ Transpose@MapThread[Map, {fns, Transpose[l]}]]]]

• using ToCharacterCode! upvote Nov 2, 2015 at 4:48

A simple approach giving the requested result is

SortBy[list, (#[[2]] /. {"u" -> 0, "d" -> 1}) + 100 #[[1]] &]
(* {{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"},
{4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}} *)


In fact, even simpler is

SortBy[list, (# /. {"u" -> 0, "d" -> 1}) &]


Simpler yet is

SortBy[list, (# /. "u" -> 0) &]


Revised AbsoluteTiming with two new solutions

With so many solutions, it may be of interest to know their respective AbsoluteTimings, based on

list = Riffle[Map[{#, "u"} &, RandomSample[Range[100000]]],
Map[{#, "d"} &, RandomSample[Range[100000]]]];


Mike Honeychurch 0.397657

J.M. (comment) 0.468703

bbgodfrey (third solution) 0.589428

belisarius is forth (first solution) 0.811408

Jack LaVigne 11.2244

Modifications of solutions by J.M. and Mike Honeychurch, respectively, are even faster.

SortBy[list, {First, Switch[#, "u", -1, "d", 1] &}]  (* 0.385315 *)

Flatten[Reverse[Partition[Sort[list], 2], 2], 1]  (* 0.25386 *)

• I like this this one, clever! But why "d" -> 1/10, "d" -> 1 is OK. A mistake? Nov 2, 2015 at 4:23
• @matheorem You are correct. "d" assigned any number bigger than that assigned to "u" works. I carried forward the logic of my first solution without thinking. Thanks for the correction. I have simplified my solution accordingly. Nov 2, 2015 at 5:05
• For large lists Sort can often be slow. Using Ordering could possibly speed up my solution for your large test sample. Nov 2, 2015 at 23:37

Your limited example implies that you want to reverse the canonical order for the letters in position 2 so that "u" will appear before "d". I've assumed that all letters of the alphabet could appear in position 2 so if that is the case then this would do it:

Flatten[Reverse[GatherBy[Sort[list], First], 2], 1]


...but there is probably a more straight forward method, perhaps using SortBy.

Edit

As mentioned in comments with @bbgodfrey it is often more efficient to use Ordering for large lists rather than Sort. Also @bbgodfrey notes that Partition could be used instead of GatherBy.

Flatten[Reverse[Partition[list[[Ordering[list]]], 2], 2], 1]

• Straightforward or not, your solution is remarkably fast, especially when GatherBy is replaced by Partition. Nov 2, 2015 at 14:14
• I just noticed a typo in my earlier comment, which is why I deleted it. Ordering[list] should have been enclosed in double-brackets, not single ones. I corrected my error in your answer. Unfortunately, with the correction list[[Ordering[list]]] offers no advantage over Sort[list], although Partition still does. Sorry. Nov 3, 2015 at 0:14
• @bbgodfrey yes you're right. Maybe Sort has been rewritten in recent versions. Certainly in older version Ordering  used to smash Sort. Nov 3, 2015 at 0:34
• On the other hand, list[[Flatten[Reverse[Partition[Ordering[list], 2], 2]]]] offers a noticeable speed advantage, probably because Reverse is acting on indices rather than on list elements. Of course, your original solution with GatherBy offers a flexibility that most other solutions lack. Nov 3, 2015 at 1:02
• @bbgodfrey I think there is enough information now to satisfy the OP Nov 3, 2015 at 1:08

I think a general solution is to perform the first test followed by the second test in case of ties.

Sort[list, first[test] || tie[first] && second[test]]


For your specific example

list = {{1, "u"}, {6, "d"}, {3, "u"}, {4, "d"}, {2, "u"}, {5, "u"},
{3, "d"}, {1, "d"}, {4, "u"}, {2, "d"}, {5, "d"}, {6, "u"}}


With the integers sorted on the first element and then "u" preceding "d" for the second element this translates to:

Sort[list, #1[[1]] < #2[[1]] ||
(#1[[1]] == #2[[1]] && OrderedQ[{#2[[2]], #1[[2]]}]) &]


which gives

{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"},
{4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}

• I believe bbgodfrey's answer is better. I see that in the documentation for SortBy it states. SortBy[list, {f1, f2}...} breaks ties by successively using the values obtained from the fi. Nov 2, 2015 at 3:55

To actually answer the question (not the specific example), you could create a recursive function. It would take a list of comparison functions, compare the first elements using the first function, and only use the rest if the first elements are the same.

ClearAll[compare];
compare[a_, b_, test_] /; Length@a == 1 := test[[1]][a[[1]], b[[1]]];
compare[a_, b_, test_] := test[[1]][a[[1]], b[[1]]] ||
a[[1]] == b[[1]] && compare[Rest@a, Rest@b, Rest@test];


In action:

Sort[list, compare[##, {Less, Greater}] &]


{{1, "u"}, {1, "d"}, {2, "u"}, {2, "d"}, {3, "u"}, {3, "d"}, {4, "u"}, {4, "d"}, {5, "u"}, {5, "d"}, {6, "u"}, {6, "d"}}

And it works with elements of any length, with any sort of comparison, e.g.

r = RandomInteger[{0, 10}, {1000, 3}];
Sort[r, compare[##, {Less, Greater, Abs[5 - #1] < Abs[5 - #2] &}] &]