14 ms·

Bubblesort is usually the worst sorting algorithm, in every conceivable way. Given that in a sorting network, bubble sort is dual to insertion sort [1], why can

Bubblesort is usually the worst sorting algorithm, in every conceivable way. Given that in a sorting network, bubble sort is dual to insertion sort [1], why can't the optimisations in the blog post be applied to insertion sort? I believe they can be, and the author was just being facetious. Stop teaching bubble sort. [1] - https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_Bubble_networks https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_...

yxhuvud 5y ago
Then I suggest you implement it and prove the author wrong by providing a benchmark where your implementation outperform the algorithm provided in the article.
moffkalast 5y ago
Absolutely right, if I had any students to teach I'd start with bogosort. It's arguably the best one.
bhaak 5y ago
If you don't believe it, benchmark it. On very small arrays bubble sort is faster than quicksort as quicksort has a large constant overhead. Constant overheads are usually disregarded in complexity analysis but in practice, it can be significant.
- deleted 5y ago
  [deleted]
- ogogmad 5y ago
  Except I was comparing bubble sort to insertion sort. Read my comment again.
  - bhaak 5y ago
    If you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).
    - ogogmad 5y ago
      You're wrong again. Insertion sort usually does less swaps than bubble sort. Question: Does it always do less swaps? Probably yes, I think.
      - FabHK 5y ago
        Part of the article (and the whole article it references) are about how algorithm A that is guaranteed to perform fewer swaps than B is nevertheless slower in practice on modern machines because of other issues (predictability, data flow). > Most contemporary implementations of quicksort use Hoare partition, for obvious reasons: it does as many comparisons as the Lomuto partition and fewer swaps. > Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. […] implemented in a branch-free manner, Lomuto partition is a lot faster than Hoare partition on random data.
OskarS 5y ago
When used as an algorithm (as opposed to a sorting network), insertion sort only inserts "as far as it needs to". In other words: it moves the new element to the correct position, then stops going back through the array. This is the aspect of insertion sort that makes it very fast for "almost sorted" data: each element is only moved a few spots. However, this is a branch that is difficult to predict: this is the author's point. For very small amounts of data, branch misprediction for this branch dominates. This is not the case when insertion sort is expressed as a sorting network. Take a look at this image [1]: the final "insert" has comparators that go through the entire network. The "algorithm" version wouldn't do that: it would stop (using a branch) as soon as the entry hits the correct place. If you remove that branch (which, remember, is the thing that makes insertion sort faster in the general case), insertion and bubble sort are indeed very similar. The point here is that "sorting algorithms" and "sorting networks" are not the same thing: a sorting algorithm can branch, a sorting network cannot. The same principles of bubbling and insertion can apply to both, but that does not mean that an insight that applies to sorting networks necessarily applies to sorting algorithms. [1]: https://en.wikipedia.org/wiki/Sorting_network#/media/File:Recursive-insertion-sorting-network.svg https://en.wikipedia.org/wiki/Sorting_network#/media/File:Re... (PS: I actually wrote most of that wikipedia article years ago! I did the illustrations too! I basically just wrote down and made diagrams for whatever I could understand from The Art of Computer Programming vol 3. The insight about how bubble sort and insertion sort are essentially the same when expressed as sorting network is from Knuth, though I doubt it's original with him)
accountLost 5y ago
I remember seeing one occurence of bubblesort in the source code of Crafty chess engine with a comment explaining that this was unexpectingly the fastest sort in that particular case. (It was the ordering of a few moves in the quiesce algorithm I think).
phkahler 5y ago
There is a nice variant of bubble sort called comb sort. It uses a variable stride between compared elements. IIRC stride = len/1.3 and then shrink it by the same amount each pass. It's way faster than plain bubble sort. I still dont know why quicksort is so common given its worst case performance.
gjm11 5y ago
The point of the article is that performance on modern hardware can be determined by things that are usually neglected in the performance analyses that tell us, e.g., that "bubblesort is usually the worst in every conceivable way". In particular, the author claims (and presents benchmarks that appear to verify) that for sorting very small arrays, bubblesort is better than insertion sort because you can do it with fewer unpredictable branches, and unpredictable branches are very bad for performance. Maybe the same optimizations can be applied to insertion sort, but it's not obvious to me that they can; in particular, the inner loop of insertion sort is of variable length and necessarily involves a hard-to-predict branch. You could do away with that by always going all the way to the end of the array, but unless I'm confused this gives you an algorithm pretty much equivalent to bubblesort, and equally worthy (according to the usual sorts of analysis) of being called "usually the worst in every conceivable way".

yxhuvud 5y ago

Then I suggest you implement it and prove the author wrong by providing a benchmark where your implementation outperform the algorithm provided in the article.

moffkalast 5y ago

Absolutely right, if I had any students to teach I'd start with bogosort. It's arguably the best one.

bhaak 5y ago

If you don't believe it, benchmark it. On very small arrays bubble sort is faster than quicksort as quicksort has a large constant overhead. Constant overheads are usually disregarded in complexity analysis but in practice, it can be significant.

deleted 5y ago
[deleted]
ogogmad 5y ago
Except I was comparing bubble sort to insertion sort. Read my comment again.
- bhaak 5y ago
  If you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).
  - ogogmad 5y ago
    You're wrong again. Insertion sort usually does less swaps than bubble sort. Question: Does it always do less swaps? Probably yes, I think.
    - FabHK 5y ago
      Part of the article (and the whole article it references) are about how algorithm A that is guaranteed to perform fewer swaps than B is nevertheless slower in practice on modern machines because of other issues (predictability, data flow). > Most contemporary implementations of quicksort use Hoare partition, for obvious reasons: it does as many comparisons as the Lomuto partition and fewer swaps. > Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. […] implemented in a branch-free manner, Lomuto partition is a lot faster than Hoare partition on random data.

OskarS 5y ago

When used as an algorithm (as opposed to a sorting network), insertion sort only inserts "as far as it needs to". In other words: it moves the new element to the correct position, then stops going back through the array. This is the aspect of insertion sort that makes it very fast for "almost sorted" data: each element is only moved a few spots. However, this is a branch that is difficult to predict: this is the author's point. For very small amounts of data, branch misprediction for this branch dominates. This is not the case when insertion sort is expressed as a sorting network. Take a look at this image [1]: the final "insert" has comparators that go through the entire network. The "algorithm" version wouldn't do that: it would stop (using a branch) as soon as the entry hits the correct place. If you remove that branch (which, remember, is the thing that makes insertion sort faster in the general case), insertion and bubble sort are indeed very similar. The point here is that "sorting algorithms" and "sorting networks" are not the same thing: a sorting algorithm can branch, a sorting network cannot. The same principles of bubbling and insertion can apply to both, but that does not mean that an insight that applies to sorting networks necessarily applies to sorting algorithms. [1]: https://en.wikipedia.org/wiki/Sorting_network#/media/File:Recursive-insertion-sorting-network.svg https://en.wikipedia.org/wiki/Sorting_network#/media/File:Re... (PS: I actually wrote most of that wikipedia article years ago! I did the illustrations too! I basically just wrote down and made diagrams for whatever I could understand from The Art of Computer Programming vol 3. The insight about how bubble sort and insertion sort are essentially the same when expressed as sorting network is from Knuth, though I doubt it's original with him)

accountLost 5y ago

I remember seeing one occurence of bubblesort in the source code of Crafty chess engine with a comment explaining that this was unexpectingly the fastest sort in that particular case. (It was the ordering of a few moves in the quiesce algorithm I think).

phkahler 5y ago

There is a nice variant of bubble sort called comb sort. It uses a variable stride between compared elements. IIRC stride = len/1.3 and then shrink it by the same amount each pass. It's way faster than plain bubble sort. I still dont know why quicksort is so common given its worst case performance.

gjm11 5y ago

The point of the article is that performance on modern hardware can be determined by things that are usually neglected in the performance analyses that tell us, e.g., that "bubblesort is usually the worst in every conceivable way". In particular, the author claims (and presents benchmarks that appear to verify) that for sorting very small arrays, bubblesort is better than insertion sort because you can do it with fewer unpredictable branches, and unpredictable branches are very bad for performance. Maybe the same optimizations can be applied to insertion sort, but it's not obvious to me that they can; in particular, the inner loop of insertion sort is of variable length and necessarily involves a hard-to-predict branch. You could do away with that by always going all the way to the end of the array, but unless I'm confused this gives you an algorithm pretty much equivalent to bubblesort, and equally worthy (according to the usual sorts of analysis) of being called "usually the worst in every conceivable way".