Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting Algorithm Cheat Sheet

interviewcake.com

Post reply on HN
Print view View original

11–20 of 52 posts

Re: Sorting Algorithm Cheat Sheet

#11

Post by strainer »

gameguy43 wrote: post #2

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

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.

Re: Sorting Algorithm Cheat Sheet

#14

Post by ggggtez »

northisup wrote: post #6

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).

Disagree. If you think that, what do you ask? "How would you Google or Stack overflow for the answer?" That's hardly going to provide any useful signal. At the end of the day you need to ask something that shows evidence there candidate knows something about efficiency tradeoffs.

Re: Sorting Algorithm Cheat Sheet

#15

Post by ggggtez »

swiftcoder wrote: post #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 on…

It's the number of bits. You can change to bytes, but you are just hiding another constant factor of 8 by doing that.

Re: Sorting Algorithm Cheat Sheet

#16

Post by CzechTech »

northisup wrote: post #6

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).

Some people like that sort of thing. Mostly the "academic" types. The memorizers. There are people who got through their higher education by using memory instead of wit. I know some of those people, I went to school with some of them, they were always studying and ramming as much "data" into their brains as possible... while I was getting through with minimum of effort by just coding a lot and trying to think about things in my own way.

The memorizers in this industry often get jobs higher up the tree and therefore they are highly represented in the hiring practices.

Anyways, I completely agree with you. In my opinion it is essential to KNOW that you DON'T KNOW (i.e. you don't remember how exactly an RB tree works, you just know there is such a thing). Everything else is just a quick Google session away.

Re: Sorting Algorithm Cheat Sheet

#17

Post by CzechTech »

saagarjha wrote: post #7
northisup wrote: post #6

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).

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.

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.

Re: Sorting Algorithm Cheat Sheet

#18

Post by bjoli »

ComputerGuru wrote: post #13

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.

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.

Re: Sorting Algorithm Cheat Sheet

#19

Post by civility »

ComputerGuru wrote: post #13

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.

Also no mention of introsort (C++ std::sort), where it uses insertion sort for small arrays, detects if it's fallen too far towards O(n^2) of quicksort, and punts to heapsort when it needs to.

Re: Sorting Algorithm Cheat Sheet

#20

Post by hinkley »

civility wrote: post #19
ComputerGuru wrote: post #13

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.

Also no mention of introsort (C++ std::sort), where it uses insertion sort for small arrays, detects if it's fallen too far towards O(n^2) of quicksort, and punts to heapsort when it needs to.

You can pry my stable sort algorithms out of my cold, dead hands.
Post reply on HN