News for hackers. Stuff that matters.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Monday August 21, 2023 @06:58AM (#37207813)
if you aren't convinced that adding the early exit generally hurts performance, well, it's not surprising; measuring performance is difficult and tricky, and you're faced here with claims you don't really have the knowledge to evaluate properly, so it's entirely proper that you are dubious about them, even if you're confused about what a proper proof would consist of

it might help your intuition to think of it this way:

1. with random input, the first ten positions of output are pretty likely (65%) to have an item that was originally in the last 10% of the input, and almost certain (97%) to have an item that was originally in the last 30% of the input. so those ten items alone account for needing 95% of the passes you'd need without an early exit, minus about five, in 65% of cases.

2. the first 20 positions are pretty likely (64%) to have an item that was originally in the last 5% of the input, and almost certain (96%) to have an item that was originally in the last 15% of the input. so those 20 items account for needing 97% of the passes you'd need without an early exit, minus about ten, in 64% of cases.

3. the first 30 positions are pretty likely (64%) to have an item that was originally in the last 3.3% of the input, and almost certain (96%) to have an item that was originally in the last 10% of the input. so those 30 items account for needing 98.5% of the passes you'd need without an early exit, minus about 15, in 64% of cases.

of course, if you're only sorting 30 items, the first ten positions of output are actually a third of all the positions, so "minus five" is pretty significant. and probably if you're sorting more than about 30 items at a time you ought to use a linearithmic sort or a linear-time radix sort instead of a quadratic sort

similarly, it's reasonable to argue that complexity (in the sense of containing many parts, not in the sense of asymptotic computational work required) is subjective, and to disagree about it

but i think these are sort of moot points

insertion sort still beats bubble sort in the situations where you have only one or two misplaced pairs of elements, and generally replaces it as soon as somebody notices

as for 'the de facto standard way of doing it today', i suggest you argue with clrs, not with me

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by SomeoneFromCA on Monday August 21, 2023 @07:19AM (#37207982)
Count number of outer passes of insertion sort (it is N) vs bubble sort (with early exit; it is 2) if you have only a single pair misplaced.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kragen on Monday August 21, 2023 @07:21AM (#37207993)
insertion sort only ever makes one outer pass; it does almost exactly half as many comparisons as bubble sort (n rather than 2n-2) in that case, and the same number of swaps (1)

the wikipedia article has a cleverer early-exit version of bubble sort that keeps track of the last pair it had to swap; it will do 1.5n-1 comparisons in that case on average (because the swapped pair is on average in the middle of the array)

above i linked to working code on godbolt (modulo the extra unnecessary swaps on duplicate keys that you were kind enough to point out earlier); edit a comparison counter and a swap counter into it and you'll see