Hacker News Reader

Comment by mort96 | Hacker News Reader

I would trust myself more to implement bubble sort than to implement insertion sort. Not that I couldn't implement insertion sort, I've done it before, but if I was in a context where I had to implement a quick and dirty ad-hoc sorting algorithm which I thought would only ever have to sort a few items, I would probably go with bubble sort.

If I suspected at all that the algorithms would have to sort a decent number of items, I wouldn't consider using an O(n^2) sort at all and would take the time to find a good implementation of (or implement) one of the O(n log(n)) algorithms.

View on HN

my subjective experience writing the above comment as documented in https://news.ycombinator.com/item?id=37206998 may be a relevant data point; note that the insertion-sort code is subtly buggy, and the bubble-sort code isn't

Pratt–Shell is only mildly more complex than insertion sort and gives a good worst-case performance O(n log(n)^2). It may have a place sometimes.

Personally I find insertion easier to reason about once you internalized the idea of a memmove.

To me, it seems like bubble sort is almost inherently easier to reason about.

One iteration of bubble sort is: find two elements in the wrong order and swap them.

One iteration of insertion sort is: find an element out of order, then find the location in the array where it should've been, then move all the items between those two slots one slot ahead, then insert the out-of-order element into the now free slot where it belongs.

Admittedly, insertion sort is pretty intuitive, since it reflects more or less how a human would instinctively try to sort a list; take an out-of-order element and move it to where it belongs. But when translated to code, I think it's very hard to beat "find two items in the wrong order and swap them".

A lot of people look at sorting algorithms with the mental model of a 1970s era PDP-8. They analyze scalar instructions as if they are being executed sequentially.

Once you admit superscalar execution (multiple loadstore pipes), out of order execution and caches into the picture ( as well as the possibility of almost sorted arrays as input) the picture is never as simple.

That said, I’m curious whether insertion sort is categorically better than bubble sort. I thought they might have been equivalent for the almost sorted case. I’ve heard both sides argued on this thread.

Per the wiki:

> Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position

In fact it’s often a sub-sort of hybrid sorts, like timsort:

> If a run is smaller than this minimum run size, insertion sort is used to add more elements to the run until the minimum run size is reached.

i think that adaptive time complexity bound holds for both bubble sort with early exit and insertion sort

the vast majority of computers still aren't superscalar, much less ooo; for every i7 there are 100 cortex-m0+s, which don't even have caches. gpus aren't superscalar or ooo either, just heavily multithreaded, simt, and simd

even if insertion sort reliably beats bubble sort on your ssd ftl chip and your wristwatch, though, it seems like there are cases on modern high-performance hardware where insertion sort is worse than bubble sort (cf. https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...) which is very surprising to me

I trust myself most to implement selection sort, its the most intuitive to me: just keep finding the next smallest element in the array and place it in its position.

I can never remember the loop bounds of bubble sort, always have to look it up.

I just remember something from basic math. Exponential curve < linear for small values.

That said a lot of time I have small arrays of objects. Instead of keeping them sorted I just grind through them to find the next largest value. That tends to be hard to get wrong.

Exponential can be better than linear for small n depending on your constant factors, but it's never a given. E.g. `2n` < `10^n + 5` for all n.

If you find yourself having to re-implement a sorting algorithm ad-hoc, you are probably using the wrong language. (Especially these days.)

...or you're implementing a kernel and don't have full access to a libc.

Who says you have to use libc?

Eg Rust has no-std crates that you can use even if you can't use the standard library.

What language should they have used instead of C?

And given that C's stdlib has a quicksort function, how would using a different language have helped?

Back then C might have been the best bet.

i think it's pretty common for a specialized reimplementation of a standard library type or function to outperform it by an order of magnitude or so in some particular case. chris wellons gave an excellent example of this with hashing in golang in https://nullprogram.com/blog/2023/06/26/

commonly (as in wellons's post about the two-sum problem) there's a variation on the standard algorithm that can help significantly, but which the standard library function doesn't have an option for

also i think the cost of reimplementing simple 'algorithms from the book' like insertion sort or even quicksort is pretty low; as you saw in my comment above, insertion sort is six lines of code and only moderately bug-prone. we aren't talking about fibonacci heaps or red-black trees or fm-indexes or rader's algorithm or something. the cost is low enough that it's easy to justify in a lot of cases

Reply on news.ycombinator.com