Posted by atan2 1 day ago
When I was playing The Farmer Was Replaced and needed to implement sorting, I just wrote a bubble sort. Worked first time.
You can also do something like a calendar queue with bubble sort for each bin.
And while I've never hit a case I would think it would have merit with data known to be pretty close to properly sorted.
Worse, big-O always hides a constant factor. What's bubblesort's constant? What's quicksort's? It wouldn't surprise me if, for small enough n (2 or 3, and maybe a bit higher), bubblesort is actually faster.
Note well: I have not actually benchmarked this.
Also note well: Determine what your n is; don't assume that it's either large or small.