Merge sort O(n log n) stable; quick sort fastest in practice; use Python sorted() which is Tim sort.
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space |
|---|
| 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) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) |
| Tim Sort (Python) | O(n) | O(n log n) | O(n log n) | O(n) |
# Merge Sort -- divide and conquer, stable O(n log n)
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: result.append(left[i]); i+=1
else: result.append(right[j]); j+=1
return result + left[i:] + right[j:]
# Quick Sort -- fastest in practice O(n log n) avg
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr)-1
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p-1)
quick_sort(arr, p+1, hi)