4 ms·

Sorting Algorithm Cheat Sheet

229 points by gameguy43 7y ago

gameguy43 7y ago
Original author here, happy to answer questions about data structures, algorithms, and coding interviews!
- pstuart 7y ago
  "No CS degree necessary." lured me in. I'm subscribed and looking forward to learning more.
- gfdhnk 7y ago
  LSB radix sort can be slow, but MSB radix sort is the fastest sorting algorithm for an array of machine words.
- strainer 7y ago
  It might be notable that on very small lists (up to around 50, maybe 100 depending on cpu/cache) insertion sort is fastest of all, even on difficult input distributions. Its so simple that cpu can skip through it rapidly. I noticed this myself and have also read other developers mention it in sort design discussions. A popular general purpose sort called 'Timsort' defaults to it for small sequences. Its possible to tweak the insert algorithm to sum distance of elements moved so far and escape to a more substantial algorithm when it gets excessive. If little rearrangement is required insertion sort is about as fast as scanning through memory can be. I think in practice the answer to the question "which should I use" (rather than "which should ideally be used") is the best developed hybrid sort library for the platform. Beyond the suitable case for insertion sort, its a really substantial job for an individual to develop, test and optimize a high performance sort library that can handle a range of distribution types.
  - btilly 7y ago
    One of the big factors behind this is that the cost of pipeline stalls in a theoretically good algorithm can significantly exceed the cost of extra comparisons. Whether that is true depends on a combination of how much data you have, what kind of data you have, and your programming language's low-level representation. For ints in C++ and a list of 20 elements, it will be reliably true. For strings in Perl with a list of 500 elements, it reliably won't be true.
saagarjha 7y ago
I think it's important to mention that counting sort and radix sort are not "true" comparison-based sorts: they have additional requirements on the input data.
- why-el 7y ago
  Indeed. Usually if you get question such as "you have an array of 1 through n", the immediate thought should be "why is it just up to n and not arbitrary numbers"? From there, you know you can get a linear sort by leveraging the mutual relationships between these numbers.
swiftcoder 7y ago
> Radix sort looks fast, with its O(n)O(n) worst-case time complexity. But, if you're using it to sort binary numbers, then there's a hidden constant factor that's usually 32 or 64 (depending on how many bits your numbers are). That's often way bigger than O(\lg(n))O(lg(n)), meaning radix sort tends to be slow in practice. The constant factor in radix sort isn't the number of bits, it's the number of digits. Since one typically sorts on a computer using 8-bit 'digits', that's a constant factor of 4 or 8 (not 32 or 64).
- ggggtez 7y ago
  It's the number of bits. You can change to bytes, but you are just hiding another constant factor of 8 by doing that.
  - swiftcoder 7y ago
    If you have a theoretical computer with single-bit registers, sure. Quicksort is also quite slow on such an computer.
    - kjeetgill 7y ago
      And this is why O() notation drops constants. 0(bits) or O(bits/8) aka bytes are the same thing. It's also worth pointing out that in standard comparison sorts, the comparison itself is technically linear to radix too, but is treated as constant. I get why it's dropped but it's worth knowing.
      - ggggtez 7y ago
        Exactly. You can try to compare two bytes, but really you are comparing 8 bits, if you thought about it algorithmically. Maybe those steps are 100% parallel. But it's irrelevant to the big O. You are measuring number of steps, and it's intended to be hardware independent.
    - ggggtez 7y ago
      Big O is hardware independent.
northisup 7y ago
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
- saagarjha 7y ago
  Sorting is such a foundational problem in computer science that pretty much every job will end up relying on the runtime of sorting algorithms. Not every job requires being able to write a bulletproof dual-partition QuickSort, of course, but knowing complexity bounds is important, even if you’re just calling your standard library’s implementation: it places fundamental bounds on what things you can improve.
  - CzechTech 7y ago
    Pretty much every job? I'd say about 10%. With all the web and web-adjacent jobs around, maybe even less. Most stdlibs are already written in a sensible way, so calling "sort" usually means calling quicksort. Most people just do not care, they have tickets and bosses to worry about.
    - nkozyra 7y ago
      Absolutely. While every job will depend on sort, so many of them will have negligible benefit by changing the least efficient algorithm to the most. And most of them just use a native language sort that does something relatively smart out of the box. It's good to write all of these at don't point so you understand why things are inefficient.
  - GordonS 7y ago
    Dev with decades of experience here - I've worked with a variety of languages and platforms, and across different domains. I'm not sure I've ever had to implement a sorting algorithm, or even had sorting as an optimisation issue (and I love micro-optimisation, a bit too much TBH!). I've had to sort things, of course, but standard (or at least "common") libraries invariably have sorting functions built-in.
marvinjames 7y ago
Best case for heapsort is actually O(n). Build heap always takes O(n). Then e.g. when all keys are the same, the max-heapify call will take O(1) instead of O(logn).
- gameguy43 7y ago
  Hmmmm good point!
ComputerGuru 7y ago
Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.
- bjoli 7y ago
  I'd say it's the other way around: you use whatever your language provides as default (which is probably something like Timsort) until it becomes a bottleneck and then you analyse the data and write something that is specific to your use case that will blow Timsort out of the water. Timsort is your first choice.
  - btilly 7y ago
    In practice this boils down to, "you use whatever your language provides". If sorting became a bottleneck, I'd literally look at every possible approach to speed it up that I could find before considering improving the sorting algorithm. Starting with trying to figure out how to throw around less data while trying to solve the problem.
    - nift 7y ago
      As someone who has spend a great deal of time on sorting algorithms when I was in academia ( even published one) I completely agree with this sentiment. Sorting algorithms are tricky to get right and there is a lot of edge cases, so even when you (think) you know what you are doing you still get it wrong. Been there many times and it always causes some frustration. Do you really want your business critical sorting rely on something that only might work? Sorting algorithms are like crypto, don't roll your own if you can avoid it.
    - bjoli 7y ago
      For a problem i faced I ended up being able to produce very small chunks of already sorted data and using the merge part of the stable sort algorithm (it was provided). Not only that, I ended up being able to do it lazily making the user experience much better.
CobrastanJorji 7y ago
feature request: make O(k) bright red, like O(n^2). As it stands, it looks nice and pleasant like O(1) but it's honkin' terrifying.
- gameguy43 7y ago
  Oh yeah, looks like we messed that up. That space complexity also doesn't even agree with the final space complexity we describe in the write up. I'm gonna actually change the space complexity in the table for both counting sort and radix sort to O(n)--that at least matches the amount of hand-waviness we used for the time costs for those two in the table.
gameguy43 7y ago
Curious: did people notice that you can click on each algorithm and click the blue button to get a detailed write up of how it works? (Or is that too hard to find?)
- strainer 7y ago
  The links to decent writeups with example code ( excellent to have) are a nice surprise when a row is expanded. On my firefox browser the paragraphs and elements in the table and writeups are somewhat excessively spaced vertically.
deleted 7y ago
[deleted]
hopscotch 7y ago
The best real sorting algorithms are often hybrid. Would be nice to see mention of parallel sorting algorithms. These have basically linear speedup and you can do them on GPUs. Obvious disclaimer that you should never care about your sorting algorithm choice until you need to. Performance is more often IO or memory related than compute. Tech interviews are daft, etc.
GorgeRonde 7y ago
There is also sorting networks. If you have to sort short list of items, it's probably the best solution around. https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network

229 points by gameguy43 7y ago

gameguy43 7y ago

Original author here, happy to answer questions about data structures, algorithms, and coding interviews!

pstuart 7y ago
"No CS degree necessary." lured me in. I'm subscribed and looking forward to learning more.
gfdhnk 7y ago
LSB radix sort can be slow, but MSB radix sort is the fastest sorting algorithm for an array of machine words.
strainer 7y ago
It might be notable that on very small lists (up to around 50, maybe 100 depending on cpu/cache) insertion sort is fastest of all, even on difficult input distributions. Its so simple that cpu can skip through it rapidly. I noticed this myself and have also read other developers mention it in sort design discussions. A popular general purpose sort called 'Timsort' defaults to it for small sequences. Its possible to tweak the insert algorithm to sum distance of elements moved so far and escape to a more substantial algorithm when it gets excessive. If little rearrangement is required insertion sort is about as fast as scanning through memory can be. I think in practice the answer to the question "which should I use" (rather than "which should ideally be used") is the best developed hybrid sort library for the platform. Beyond the suitable case for insertion sort, its a really substantial job for an individual to develop, test and optimize a high performance sort library that can handle a range of distribution types.
- btilly 7y ago
  One of the big factors behind this is that the cost of pipeline stalls in a theoretically good algorithm can significantly exceed the cost of extra comparisons. Whether that is true depends on a combination of how much data you have, what kind of data you have, and your programming language's low-level representation. For ints in C++ and a list of 20 elements, it will be reliably true. For strings in Perl with a list of 500 elements, it reliably won't be true.

saagarjha 7y ago

I think it's important to mention that counting sort and radix sort are not "true" comparison-based sorts: they have additional requirements on the input data.

why-el 7y ago
Indeed. Usually if you get question such as "you have an array of 1 through n", the immediate thought should be "why is it just up to n and not arbitrary numbers"? From there, you know you can get a linear sort by leveraging the mutual relationships between these numbers.

swiftcoder 7y ago

> Radix sort looks fast, with its O(n)O(n) worst-case time complexity. But, if you're using it to sort binary numbers, then there's a hidden constant factor that's usually 32 or 64 (depending on how many bits your numbers are). That's often way bigger than O(\lg(n))O(lg(n)), meaning radix sort tends to be slow in practice. The constant factor in radix sort isn't the number of bits, it's the number of digits. Since one typically sorts on a computer using 8-bit 'digits', that's a constant factor of 4 or 8 (not 32 or 64).

ggggtez 7y ago
It's the number of bits. You can change to bytes, but you are just hiding another constant factor of 8 by doing that.
- swiftcoder 7y ago
  If you have a theoretical computer with single-bit registers, sure. Quicksort is also quite slow on such an computer.
  - kjeetgill 7y ago
    And this is why O() notation drops constants. 0(bits) or O(bits/8) aka bytes are the same thing. It's also worth pointing out that in standard comparison sorts, the comparison itself is technically linear to radix too, but is treated as constant. I get why it's dropped but it's worth knowing.
    - ggggtez 7y ago
      Exactly. You can try to compare two bytes, but really you are comparing 8 bits, if you thought about it algorithmically. Maybe those steps are 100% parallel. But it's irrelevant to the big O. You are measuring number of steps, and it's intended to be hardware independent.
  - ggggtez 7y ago
    Big O is hardware independent.

northisup 7y ago

Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).

saagarjha 7y ago
Sorting is such a foundational problem in computer science that pretty much every job will end up relying on the runtime of sorting algorithms. Not every job requires being able to write a bulletproof dual-partition QuickSort, of course, but knowing complexity bounds is important, even if you’re just calling your standard library’s implementation: it places fundamental bounds on what things you can improve.
- CzechTech 7y ago
  Pretty much every job? I'd say about 10%. With all the web and web-adjacent jobs around, maybe even less. Most stdlibs are already written in a sensible way, so calling "sort" usually means calling quicksort. Most people just do not care, they have tickets and bosses to worry about.
  - nkozyra 7y ago
    Absolutely. While every job will depend on sort, so many of them will have negligible benefit by changing the least efficient algorithm to the most. And most of them just use a native language sort that does something relatively smart out of the box. It's good to write all of these at don't point so you understand why things are inefficient.
- GordonS 7y ago
  Dev with decades of experience here - I've worked with a variety of languages and platforms, and across different domains. I'm not sure I've ever had to implement a sorting algorithm, or even had sorting as an optimisation issue (and I love micro-optimisation, a bit too much TBH!). I've had to sort things, of course, but standard (or at least "common") libraries invariably have sorting functions built-in.

marvinjames 7y ago

Best case for heapsort is actually O(n). Build heap always takes O(n). Then e.g. when all keys are the same, the max-heapify call will take O(1) instead of O(logn).

gameguy43 7y ago
Hmmmm good point!

ComputerGuru 7y ago

Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.

bjoli 7y ago
I'd say it's the other way around: you use whatever your language provides as default (which is probably something like Timsort) until it becomes a bottleneck and then you analyse the data and write something that is specific to your use case that will blow Timsort out of the water. Timsort is your first choice.
- btilly 7y ago
  In practice this boils down to, "you use whatever your language provides". If sorting became a bottleneck, I'd literally look at every possible approach to speed it up that I could find before considering improving the sorting algorithm. Starting with trying to figure out how to throw around less data while trying to solve the problem.
  - nift 7y ago
    As someone who has spend a great deal of time on sorting algorithms when I was in academia ( even published one) I completely agree with this sentiment. Sorting algorithms are tricky to get right and there is a lot of edge cases, so even when you (think) you know what you are doing you still get it wrong. Been there many times and it always causes some frustration. Do you really want your business critical sorting rely on something that only might work? Sorting algorithms are like crypto, don't roll your own if you can avoid it.
  - bjoli 7y ago
    For a problem i faced I ended up being able to produce very small chunks of already sorted data and using the merge part of the stable sort algorithm (it was provided). Not only that, I ended up being able to do it lazily making the user experience much better.

CobrastanJorji 7y ago

feature request: make O(k) bright red, like O(n^2). As it stands, it looks nice and pleasant like O(1) but it's honkin' terrifying.

gameguy43 7y ago
Oh yeah, looks like we messed that up. That space complexity also doesn't even agree with the final space complexity we describe in the write up. I'm gonna actually change the space complexity in the table for both counting sort and radix sort to O(n)--that at least matches the amount of hand-waviness we used for the time costs for those two in the table.

gameguy43 7y ago

Curious: did people notice that you can click on each algorithm and click the blue button to get a detailed write up of how it works? (Or is that too hard to find?)

strainer 7y ago
The links to decent writeups with example code ( excellent to have) are a nice surprise when a row is expanded. On my firefox browser the paragraphs and elements in the table and writeups are somewhat excessively spaced vertically.

deleted 7y ago

[deleted]

hopscotch 7y ago

The best real sorting algorithms are often hybrid. Would be nice to see mention of parallel sorting algorithms. These have basically linear speedup and you can do them on GPUs. Obvious disclaimer that you should never care about your sorting algorithm choice until you need to. Performance is more often IO or memory related than compute. Tech interviews are daft, etc.

GorgeRonde 7y ago

There is also sorting networks. If you have to sort short list of items, it's probably the best solution around. https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network