I had a problem where I wanted to sort a list of tuples, first by the first element and then by the second.

I found that with Python it's pretty easy - SO answer

My question is how does this work internally? What's the complexity of sorting by 2 fields? Can we generalize the answer for k fields?

CodePudding user response：

This has no effect on the overall complexity of sorting.

Pick any comparison-based sorting algorithm, and give it the correct comparison function for sorting according to your 2 (or k) fields.

The best comparison sorts have complexity O(n log n) in terms of comparison operations. So if you have k fields to compare, the new complexity is O(k * n log n), but k is constant relative to n so can be excluded depending on what exactly you want to know.

The downside is that you can't use other sorting algorithms in the same way (like counting sort, bucket sort, radix sort, ...) since they don't accept a comparison function. You could provide a function that ranks all pairs or k-tuples of fields in an ordered fashion: it would produce an integer per element and you can then sort these integers.

You could also, as rici mentions, run a stable sorting algorithm (not necessarily comparison-based) k times on each field, from the field that matters the least to the one that matters the most. Because each sort is stable, it will keep the previous order when two elements compare equal, so by the end the order is correct for every field.