Sorting Algorithm Cheat Sheet
interviewcake.com
Sorting Algorithm Cheat Sheet
1–10 of 52 posts
Re: Sorting Algorithm Cheat Sheet
#2Original author here, happy to answer questions about data structures, algorithms, and coding interviews!
Re: Sorting Algorithm Cheat Sheet
#3I 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.
Re: Sorting Algorithm Cheat Sheet
#4Original author here, happy to answer questions about data structures, algorithms, and coding interviews!
"No CS degree necessary." lured me in. I'm subscribed and looking forward to learning more.
Re: Sorting Algorithm Cheat Sheet
#5> 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).
Re: Sorting Algorithm Cheat Sheet
#6Who 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).
Re: Sorting Algorithm Cheat Sheet
#7Who 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).
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.
Re: Sorting Algorithm Cheat Sheet
#8Original author here, happy to answer questions about data structures, algorithms, and coding interviews!
LSB radix sort can be slow, but MSB radix sort is the fastest sorting algorithm for an array of machine words.
Re: Sorting Algorithm Cheat Sheet
#9I 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.
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.
Re: Sorting Algorithm Cheat Sheet
#10Who 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).
I see your point, and usually these work best if the interviewer can prove that such a thing is needed. For instance, many jobs might require sorting of data that cannot fit on disk (think for instance of loading a massive file that you want to parse, and sorting might help you in processing it), in which case knowing merge sort (the disk variety) can help. So yes, the onus is on the interviewer I think.