33. Compare the common sorting algorithms.
MediumSorting
Technical
Show model answer
Bubble, selection and insertion sort are O(n²); insertion sort is fast on small or nearly sorted input and is stable. Merge sort is O(n log n) always, stable, and uses O(n) extra space. Quicksort averages O(n log n), is in place, but worst-case O(n²). Heap sort is O(n log n) in place but not stable.
Counting, radix and bucket sort beat O(n log n) by not comparing elements, but only for restricted inputs (small integer ranges or uniform distributions). Comparison sorts cannot beat Ω(n log n) in the worst case.