N^2 or N^3 is fine for things that are fixed size and very unlikely to stop being fixed size, or at least unlikely to grow a lot. But any time you think "oh it's just a few files" when there is nothing to stop it from being 1000 files in ten years, or at one rare user: don't use an O(N^2) solution.

No, it’s just a non-issue in the 99% of cases where it really does stay at small inputs. I come across configuration code all of the time that is stupidly inefficient like this and it’s almost always irrelevant. Tons of stuff works on inputs of <10.

Adding complexity because of an anticipation that some input will grow to an unreasonable size (at the time of writing) may or may not be a good idea. But using a different off the shelf function or data structure is usually not a high cost for making sure it's not a problem down the line. Of course, that also assumes that there is a good and efficient standard lib of methods and data structures so that "making a more clever choice" isn't also a burden or risk in terms of code size, complexity, risk of bugs.

For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.

And it was a blatant O(n) algorithm, easily swapped out, it’s not like they were calling sscanf in a loop and whoopsie turns out C strings are shit so now parsing a 4 characters decimal number is O(buflen^2).

Properly predicting if it will be fine or not is a sign of wisdom. But something like this is a fine place to use something where the complexity blows up. The sort happens in a clear place; early boot is a little hard to debug, but still. It's much worse when you put something N^3 in where when it blows up, the time spent is diffuse.

- it's constant time or it's crap

- constant time means your best case is as slow as your worst case

In this case, constant time would be sorting it before the program runs.

Which is in fact important in crypto code to prevent timing attacks.

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 1; j < n - i; j++) {
            if (a[j-1] > a[j]) {
                item_t tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }

    for (size_t i = 1; i < n; i++) {
        for (size_t j = i; j > 0; j--) {
            item_t tmp = a[j];
            if (tmp > a[j-1]) break;
            a[j] = a[j-1];
            a[j-1] = tmp;
        }
    }

(above code only minimally tested: https://godbolt.org/z/43dqz9Gq8)

this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you'd never ship anything. freebsd's code quality is quite high, but probably we can all agree that this was stupid

of course it wouldn't be nearly as fast as mergesort on large inputs, but mergesort is more complicated

(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you're only sorting something once at startup time, that probably isn't important. it might matter if you were sorting a million lists of ten items or something)

even the best of us do stupid things sometimes

And maybe it wasn't 'no additional effort' because they were more confident with quickly writing a bubble sort.

It also could have been apathy: knowing there was a better solution and just not caring what was implemented. I feel like this is more common than incompetence, especially in larger projects or organizations. Nature tends to take the path of least resistance.

Not if it was already written.

I don't know anything about this particular codebase, but one thing I have learned over the years is that when you are tempted to say "such and such decision was stupid" in a production codebase, you are almost always missing something.

Of course there are valid values below that...

If they were designing to a collection size of N -> ∞ then they shouldn't have used Insertion Sort either then, because it is O(n²) in the worst case.

It's trivial to start with something that gets human input and someone, somewhere, decides to plug the thing into something else that generates that input.

And we all know that if computers are good at something, it's doing a lot of small things millions of times.

Besides there's little reason for any codebase of any kind of ever contain bubble sort (except for an academic one, showing it as an example of a bad one). We're talking 20 years ago, not 2000 years ago, the basic sorting algorithms were pretty well researched and established by then.

Since what insertion sort is faster that bubble sort on sorted data?

admittedly this was probably after you wrote your comment

You should probably check wikipedia page. Here: https://en.wikipedia.org/wiki/Bubble_sort.

it's true that, if your data is exactly sorted, or has a small number of items that are far too early (e.g., 43 3 4 5 6 7 8 9 10), you can modify bubble sort to notice this and exit early, at the expense of making it more complicated and even slower in the average case

however, this doesn't help if instead you have a small number of items that are far too late (e.g., 4 5 6 7 8 9 10 43 3), in which case bubble sort takes the same number of passes as it normally would, while insertion sort takes linear time. of course you can complicate bubble sort further into "shaker sort" to handle this, which makes it even more complicated but at least doesn't slow it down any further

but all of this is sort of futile because it's still half as fast as insertion sort in the case of unsorted input, and even without the tweaks, no simpler

bubble sort with early exit is

    for (size_t i = 0; i < n; i++) {
        bool sorted = 1;
        for (size_t j = 1; j < n - i; j++) {
            if (a[j-1] > a[j]) {
                item_t tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                sorted = 0;
            }
        }
        if (sorted) break;
    }

if you compile it https://godbolt.org/z/jdzov8cPn you can see that the inner loop goes from 10 instructions to 11. that doesn't guarantee that it's 9% slower (that depends a lot on the platform, and in particular on a big superscalar cpu it probably just uses a little more power but the same number of clocks) but it does tend in that direction. of course occasionally it will save you a pass or two over the array, which will tend to compensate, but it won't usually save you 9% of the passes

if some item is in position n and needs to be in position m, where m < n, it will require n - m passes of bubble sort to get there. a little thought suffices to show that, for randomly shuffled input, where m = 0 the item has to move about half the size of the array, where m = 1 it has to move about half the size of the array minus one half, where m = 2 it has to move about half the size of the array minus one; but it's the maximum of these three numbers which determines the number of passes after which all three of those positions will have the correct item, and that maximum is heavily skewed to be almost the entire size of the array. the chance that none of those three items is in the last 25% of the array originally is only .75*3 = 42%. and as the value of three increases, it gets worse. so in general early exit doesn't buy you much

as for modern implementations of bubble sort, they're all either didactic classroom exercises like this one or careless mistakes like the original freebsd code; because insertion sort always beats it, there aren't like a community of bubble sort implementors who have annual bubble sort conferences

Although I certainly agree that Bubble Sort is almost always a bad choice, it still is used in computer graphics, or other situations when you have only one or two misplaced pairs of elements. In this case it will outperform the other algorithms, in average case while maintainig functionally in the less than ideal situation.

Besides it is entirely irrelevant what are the purposes the algorithm is used today, didactic, deliberate or poor judgement, the de facto standard way of doing it today is to check for the early exit. Your argument about poor performance on the already sorted data is a straw man argument, your are stubbornly defending. Well ok, if you believe so...

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

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

someone else might have written the original version, i can't remember any more, but i think it was probably me

It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.)

The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.

it should say

    if (tmp >= a[j-1]) break;

  /*
  *
  * Perform a bubble sort of the system initialization objects by
  * their subsystem (primary key) and order (secondary key).
  */
 TSENTER2("bubblesort");
 for (sipp = sysinit; sipp < sysinit_end; sipp++) {
  for (xipp = sipp + 1; xipp < sysinit_end; xipp++) {
   if ((*sipp)->subsystem < (*xipp)->subsystem ||
        ((*sipp)->subsystem == (*xipp)->subsystem &&
         (*sipp)->order <= (*xipp)->order))
    continue; /* skip*/
   save = *sipp;
   *sipp = *xipp;
   *xipp = save;
  }
 }
 TSEXIT2("bubblesort");

There you have your problem: any programmer can write a bubble sort while half asleep and inebriated at the same time, but for an insertion sort you actually have to think a little. There's much more chance of errors.

(FreeBSD got a test suite in 10.1, which came out in 2014, not that long ago in UNIX terms.)

People would be shocked by how little the core tools we use were tested automatically. Some still aren't.

Thankfully the practice of just randomly shelling out to 'random' programs (like the core tools) has been stemmed somewhat, so perhaps we're mostly safe from RCE via that vector. Downloaded files might still be a vector, tho. Maybe I'm an optimist even though I sound very pessimistic.

I dunno what FreeBSD's test infrastructure is, but I'm just saying that "it needs testing" is not a good reason not to change to a better sort algorithm in this case.

if your interests run the other way, that's great, and hopefully you will succeed in improving freebsd's testing infrastructure, but it's hardly a reason for colin not to speed up booting

but i don't think i saw anyone claiming that the change should not be made because it wouldn't be adequately tested?

Quote:

> will be reviewed and tested by 200 people before it reaches production

I was only saying that this is a bad argument for any simple-ish sorting algorithm.

(Granted, if you're doing super-complicated sorting algos with fallbacks for different sizes, heurestics for detecting semi-sorted input, etc. you might want something more sophisticated than trivial property-based checking.)

edited to add: someonefromca spotted a bug in the insertion sort; where it says

    if (tmp > a[j-1]) break;

    if (tmp >= a[j-1]) break;

Maybe a fair judge of mental difficulty would say "you gotta write at least the loop invariant" (termination being too pedantically obvious) -- though admittedly I leave it out more than I used to.

When I was introduced to sorting as a new programmer, via bubblesort, I thought "why that way?" and came up with selection sort as a method that made more obvious sense. It seems to me like bubblesort's alleged intuitiveness is post hoc from the shortness of the code in terms of all-ascending for-next loops -- the intuitive reason it worked was just that the inner loop did move the next max into place just like selection sort, but with extra swaps along the way.

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.

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

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.

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

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

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

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

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

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

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.

I used to believe this but then a friend pointed out a real use case for bubble sort: when you have an array that is always mostly sorted, and real-time performance is more important than perfectly correct ordering. Then running one pass of bubble sort each cycle around the main loop is somewhat satisfyingly ideal.

One pass of insertion sort would be too expensive, and bubble sort is guaranteed to make incremental progress each pass.

Most sorts are designed to "really sort something", however I'm very interested in eg: ranking preferences of movies, and in cases like that there may never be "the one true ordering" ... however the mechanism for getting things "closer to sorted" is incredibly close to the mechanism you mentioned: multiple passes, and continual, incremental progress.

My imaginary GUI for interactive sorting in this manner is something like starting with a few "A vs. B" of a generally accepted "top 10/100 vs generic v pretty bad", and then morph to a "drag this new movie in between a few other movies either above, between, or below"

There are sorting algorithms for computers (eg: compare + swap), but fewer sorting algorithms for humans (eg: bucket sort / postman's sort - https://en.wikipedia.org/wiki/Bucket_sort#Postman's_sort ) which can take advantage of "not just compare and swap" to get things "close to correct" quicker.

Abstract-This paper considers the reduction in algorithmic complexity that can be achieved by permitting approximate answers to computational problems. It is shown that Shannon’s rate-distortion function could, under quite general conditions, provide lower bounds on the mean complexity of inexact computations. As practical examples of this approach, we show that partial sorting of N items, insisting on matching any non zero fraction of the terms with their correct successors, requires 0 (N log N) comparisons. On the other hand, partial sorting in linear time is feasible (and necessary) if one permits any finite fraction of pairs to remain out of order. It is also shown that any error tolerance below 50 percent can neither reduce the state complexity of binary N-sequences from the zero-error value of O(N) nor reduce the combinational complexity of N-variable Boolean functions from the zero-error level of 0(2N/N).

When humans are tasked with the comparison, it doesn't have to be strictly pair-wise and instead can devolve (kindof) into the various kinds of "sorting networks" that minimize the cmp-swap given a limited subset of the list.

Thanks for the reference!

There _could_ be arguments against some sorts, e.g. less predictable memory or performance. But qsort is pretty well behaved.

        /*
         * Perform a bubble sort of the system initialization objects by
         * their subsystem (primary key) and order (secondary key).
         *
         * Since some things care about execution order, this is the
         * operation which ensures continued function.
         */
        for( sipp = (struct sysinit **)sysinit_set.ls_items; *sipp; sipp++) {
                for( xipp = sipp + 1; *xipp; xipp++) {
                        if( (*sipp)->subsystem < (*xipp)->subsystem ||
                            ( (*sipp)->subsystem == (*xipp)->subsystem &&
                              (*sipp)->order < (*xipp)->order))
                                continue;       /* skip*/
                        save = *sipp;
                        *sipp = *xipp;
                        *xipp = save;
                }
        }

selection sort has the potential advantage for things that are larger than your key that it can avoid copying the entire item, just doing a single swap at the end of the inner loop, but it's not implemented that way here. that would have looked like this

    size_t m = 0;
    register unsigned int subsystem = (*sipp)->subsystem;
    register unsigned int order = (*sipp)->order;
    for( xipp = sipp + 1; *xipp; xipp++) {
        register unsigned int newsubsystem = (*xipp)->subsystem;
        register unsigned int neworder = (*xipp)->order;
        if( subsystem < newsubsystem ||
            (subsystem == newsubsystem && order < neworder))
                  continue;       /* skip*/
        m = xipp - sipp;
        subsystem = newsubsystem;
        order = neworder;  /* enjoy the sorting */
    }

    save = sipp[0];
    sipp[0] = sipp[m];
    sipp[m] = save;

Not true. Bubble sort is excellent for sorting very small arrays.

See "Hoare’s Rebuttal and Bubble Sort’s Comeback (2020)" under "Fallback for sorting short arrays" and the performance results presented therein [0]. Discussion [1].

[0]: https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...

[1]: https://news.ycombinator.com/item?id=23363165

all of the bubble sorts i tried compiling in this thread ended up being compiled to code with either conditional branches or (on arm thumb-2) a couple of conditionalized stores. but conditional stores don't require a pipeline flush, and it is of course perfectly correct that insertion sort depends on its inner loop having an unpredictable branch to get better performance on almost-sorted data, which bubble sort does not

python version of the inner loop

    max_ = arr[0]
    for j in range(1, i):
        y = arr[j]
        arr[j - 1] = min(max_, y)
        max_ = max(max_, y)

    arr[i - 1] = max_