Hacker News Reader

Comment by mort96 | Hacker News Reader

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

View on HN

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

Reply on news.ycombinator.com