Sorting
Insertion sort vs Quick sort
Insertion sort and Quick sort both put an array in order, in different ways. Insertion sort: insert each value into a sorted prefix. Quick sort: divide and conquer: partition around a pivot. In the worst case both take O(n²), so the choice comes down to the other differences below.
At a glance
| Property | Insertion sort | Quick sort |
|---|---|---|
| Technique | Insert each value into a sorted prefix | Divide and conquer: partition around a pivot |
| Best case time | O(n) | O(n log n) |
| Average case time | O(n²) | O(n log n) |
| Worst case time | O(n²) | O(n²) |
| Extra space | O(1) | O(log n) |
| Stable (equal values keep their order) | Yes | No |
| In place (no extra array) | Yes | Yes |
| Needs sorted input | No | No |
When to choose each
Choose insertion sort when
the array is small or nearly sorted.
Avoid it when
the array is large and in random order.
Choose quick sort when
you want a fast in-place sort on typical data.
Avoid it when
you need a worst-case guarantee or a stable sort.
The same inputs, counted
These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes).
| Input | Insertion sort | Quick sort |
|---|---|---|
| Mixed | 30 | 31 |
| Already sorted | 12 | 75 |
| Reversed | 48 | 51 |
| Nearly sorted | 14 | 65 |
| Duplicates | 36 | 29 |
See them run
More comparisons
- Bubble sort vs Selection sort
- Bubble sort vs Insertion sort
- Bubble sort vs Merge sort
- Bubble sort vs Quick sort
- Bubble sort vs Heap sort
- Bubble sort vs Counting sort
- Bubble sort vs Radix sort
- Selection sort vs Insertion sort
- Selection sort vs Merge sort
- Selection sort vs Quick sort
- Selection sort vs Heap sort
- Selection sort vs Counting sort
- Selection sort vs Radix sort
- Insertion sort vs Merge sort
- Insertion sort vs Heap sort
- Insertion sort vs Counting sort
- Insertion sort vs Radix sort
- Merge sort vs Quick sort
- Merge sort vs Heap sort
- Merge sort vs Counting sort
- Merge sort vs Radix sort
- Quick sort vs Heap sort
- Quick sort vs Counting sort
- Quick sort vs Radix sort
- Heap sort vs Counting sort
- Heap sort vs Radix sort
- Counting sort vs Radix sort