3 ms·
Keep in mind that big-O notation describes how something behaves as the problem size goes up. Something O(n^2) will be slower than something that is O(n log(n))
by tzs 7y ago
Keep in mind that big-O notation describes how something behaves as the problem size goes up. Something O(n^2) will be slower than something that is O(n log(n)) for large enough n. For smaller n, it is quite possible that an O(n^2) algorithm can beat an O(n log(n)) one.
If you have an application that only has to sort small lists, but has to sort a lot of them, it is quite possible that an O(n^2) sort like bubble, insertion, or selection sort will be better than merge/quick sort.
Among the O(n^2) sorts, insertion almost always will be faster than bubble, so you probably wouldn't actually choose bubble sort.
- Gunax 7y agoI understand. In a sense merge/quick are 'galactic algorithms' at the size. It's more just that I am concerned I would be cornered trying to remember what 'bubble sort' is. It's not difficult to write the algorithm per se--just hard to remember what 'bubble sort' means.