4 ms·
In an aside he mentions you should use bubblesort instead of quicksort for small arrays, due to cache locality, etc. I'd recommend using insertion sort instead
by pbiggar 15y ago
In an aside he mentions you should use bubblesort instead of quicksort for small arrays, due to cache locality, etc. I'd recommend using insertion sort instead of bubblesort - it does much better in both cache locality and branch performance (one branch prediction miss per key).
- cobrausn 15y agoThat seems a strange assertion - I was under the impression that insertion sort beats bubble sort on small arrays, pretty much always, and even in 'nearly sorted' arrays, which is often touted as a strength of bubble sort. http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ gives a decent overview with n equal to 20, 30, 40, or 50, but nothing smaller. Now I'm curious.