0

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?

greenButMellow
  • 316
  • 1
  • 9
  • 2
    It works **exactly the same** as "normal" sorting. In theory the time complexity is simply k * normal complexity since each object comparison now does not "cost" just 1 but k if you are unlucky and all first elements are equal. But one could argue that this does not matter since it just is a constant factor and therefore irrelevant. – luk2302 Oct 09 '22 at 15:50

1 Answers1

2

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.

Nelfeal
  • 12,593
  • 1
  • 20
  • 39
  • 1
    This should be `O(kn log n)`, not `log nk`, because the algorithm still only performs `O(n log n)` comparisons and each comparison takes `O(k)` time. – kaya3 Oct 09 '22 at 15:56
  • 1
    If your "other sorting algorithm" is stable -- and the ones you mention are -- then you can just run the sort `k` times, each time on a single component, working *backwards* (that is, last component first). – rici Oct 09 '22 at 17:59