This is a list of easy C++ basic sorting algorithms as well as a way to benchmark them one to another. Feel free to reuse this bits of code in any future project !
Algorithms in speed order asymptotically (tested on random array data, c.f. benchmarks)
| Algorithm | Worst time complexity | Average time complexity | Best time complexity | Memory usage | Implementation difficulty | Speed on random arrays |
|---|---|---|---|---|---|---|
| Quick Sort | O(n^2) |
O(nlogn) |
O(nlogn) |
O(logn) |
★★★★ | The fastest overall, beats all the other, even Merge Sort (by a thin margin though). |
| Merge Sort | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
★★★ | Almost as fast as Quick Sort, beats also all the others below, is quite a lot faster than Heap Sort strangely enough. |
| Heap Sort | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
★★★★★ | Theoretically the fastest of all, but in reality it's beaten by Quick Sort and Merge Sort though it still beats Insertion/Selection/Bubble sort by a mile anytime, plus it's a nice algorithm IMO. |
| Selection Sort | O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
★★ | Quite slow, but beats Insertion Sort (by a thin margin) and of course beats Bubble Sort. |
| Insertion Sort | O(n) |
O(n^2) |
O(n^2) |
O(1) |
★★ | Same as selection sort in all aspects, except that in the best case it's linear which means it beats every other algorithm if the array is already sorted, therefore it's nice to use on small arrays at the end of a Merge Sort for instance. |
| Bubble Sort | O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
★ | Arguably the slower of all sorting algorithm (except esotheric attempts like Boggo Sort). Many consider this the easiest to implement, though I'd say Insertion/Selection is a more obvious way of doing it intuitively. |
