Algorithms · Sorting
Sort the same array in eight different ways
All methods start with [6, 2, 8, 4, 9, 1, 5]. Choose one and follow each step.
O(n²) · Simple, but slower
O(n log n) · Divide for speed
Without comparisons
Compare at a glance
| Method | Average | Worst | Extra space | Preserves equal-value order |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | No |
| Shell Sort | O(n log² n) | O(n²) | O(1) | No |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(k) | Yes |
Bubble SortAverage O(n²) · Worst O(n²) · Extra space O(1) · Stable YesInsertion SortAverage O(n²) · Worst O(n²) · Extra space O(1) · Stable YesSelection SortAverage O(n²) · Worst O(n²) · Extra space O(1) · Stable NoShell SortAverage O(n log² n) · Worst O(n²) · Extra space O(1) · Stable NoQuick SortAverage O(n log n) · Worst O(n²) · Extra space O(log n) · Stable NoMerge SortAverage O(n log n) · Worst O(n log n) · Extra space O(n) · Stable YesHeap SortAverage O(n log n) · Worst O(n log n) · Extra space O(1) · Stable NoCounting SortAverage O(n + k) · Worst O(n + k) · Extra space O(k) · Stable Yes