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;
}
}
}
when you could use insertion sort 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;
}
}
which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases(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)