Sorting algorithms
Compare how sorting algorithms use time and memory. Then follow Quick Sort one step at a time.
Time and space
The table shows how work and extra memory grow when the list gets larger. n is the number of values.
| Algorithm | Best case | Average case | Worst case | Extra space |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) typical; O(n) worst |
Bubble Sort reaches O(n) in the best case only when it stops early after a pass with no swaps. Quick Sort’s extra space includes memory for its recursive calls.
Quick Sort, step by step
Choose Next to see why each value stays or moves. The last value in each part is the pivot.