Sorting Algorithms
Core sorting algorithms — what they do, pseudocode, and complexity.
Bubble Sort
Repeatedly swaps adjacent elements if out of order. Each pass pushes the largest unsorted element to its correct position.
- Use case: Educational only. Never production.
- Stable: Yes
for i from 0 to n-1:
for j from 0 to n-i-2:
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n) | O(n²) | O(n²) | O(1) |
Selection Sort
Finds the minimum in the unsorted portion and places it at the front. Performs the fewest swaps.
- Use case: When write operations are costly.
- Stable: No
for i from 0 to n-1:
minIdx = i
for j from i+1 to n:
if arr[j] < arr[minIdx]: minIdx = j
swap(arr[i], arr[minIdx])
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n²) | O(n²) | O(n²) | O(1) |
Insertion Sort
Builds sorted array one element at a time by shifting larger elements right.
- Use case: Small or nearly sorted datasets.
- Stable: Yes
for i from 1 to n:
memo = arr[i]
j = i - 1
while j >= 0 and arr[j] > memo:
arr[j+1] = arr[j]
j--
arr[j+1] = memo
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n) | O(n²) | O(n²) | O(1) |
Merge Sort
Divide and conquer. Splits array in half recursively, merges sorted halves. Guaranteed O(n log n).
- Use case: Linked lists, external sorting, stability required.
- Stable: Yes
mergeSort(arr):
if len(arr) <= 1: return arr
mid = len(arr) / 2
left = mergeSort(arr[0..mid])
right = mergeSort(arr[mid..n])
return merge(left, right)
merge(left, right):
result = []
while left and right non-empty:
append the smaller of left[0] or right[0]
append remaining elements
return result
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n log n) | O(n log n) | O(n log n) | O(n) |
Quick Sort
Picks a pivot, partitions elements around it, recursively sorts each side. Fast in practice.
- Use case: General-purpose in-place sorting. Default in most standard libraries.
- Stable: No
quickSort(arr, low, high):
if low < high:
p = partition(arr, low, high)
quickSort(arr, low, p - 1)
quickSort(arr, p + 1, high)
partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j from low to high-1:
if arr[j] <= pivot:
i++
swap(arr[i], arr[j])
swap(arr[i+1], arr[high])
return i + 1
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n log n) | O(n log n) | O(n²) | O(log n) |
Worst case hits on sorted input with naive pivot. Use random pivot or median-of-three to mitigate.
Heap Sort
Builds a max-heap, then repeatedly extracts the max to sort in place.
- Use case: O(n log n) guaranteed with O(1) extra space.
- Stable: No
heapSort(arr):
buildMaxHeap(arr)
for i from n-1 to 1:
swap(arr[0], arr[i])
heapify(arr, 0, i)
heapify(arr, i, size):
largest = i
left = 2*i + 1, right = 2*i + 2
if left < size and arr[left] > arr[largest]: largest = left
if right < size and arr[right] > arr[largest]: largest = right
if largest != i:
swap(arr[i], arr[largest])
heapify(arr, largest, size)
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n log n) | O(n log n) | O(n log n) | O(1) |
Counting Sort
Non-comparison sort. Counts element occurrences, reconstructs sorted output.
- Use case: Integer keys in a small, known range.
- Stable: Yes
countingSort(arr, maxVal):
count[0..maxVal] = 0
for each x in arr: count[x]++
for i from 1 to maxVal: count[i] += count[i-1]
for x in reverse(arr):
output[count[x]-1] = x
count[x]--
return output
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(n+k) | O(n+k) | O(n+k) | O(k) |
k = range of input. Breaks down when k >> n.
Radix Sort
Sorts integers digit by digit (LSD → MSD) using a stable sub-sort per digit.
- Use case: Large datasets of fixed-length integers or strings.
- Stable: Yes
radixSort(arr):
for each digit position d (LSD to MSD):
stably sort arr by digit d // typically Counting Sort
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Complexity | O(nk) | O(nk) | O(nk) | O(n+k) |
k = number of digits. Efficient when k is constant (e.g., 32-bit integers).
Quick Reference
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ❌ |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ |
| Radix | O(nk) | O(nk) | O(nk) | O(n+k) | ✅ |