Sorting Algorithms

Each algorithm includes Python and C++ implementations with time/space complexity analysis.

Merge Sort

Stable divide-and-conquer sort with O(n log n) time and O(n) extra space.

How it works

Merge Sort divides the array into halves recursively until single elements remain, then merges them back in sorted order. It's stable (preserves relative order of equal elements) and guarantees O(n log n) performance. The key insight is that merging two sorted arrays takes linear time, making the overall algorithm efficient.

Time Complexity

O(n log n)

Space Complexity

O(n)

def merge_sort(a):
  if len(a) <= 1: return a
  mid = len(a)//2
  left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
  i = j = 0; res = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]: res.append(left[i]); i += 1
    else: res.append(right[j]); j += 1
  return res + left[i:] + right[j:]

Quick Sort

In-place partition-based sort; average O(n log n), worst O(n^2) without careful pivot selection.

How it works

Quick Sort uses a pivot element to partition the array into smaller and larger elements, then recursively sorts each partition. It's in-place (uses O(log n) extra space for recursion) and has excellent average-case performance. The choice of pivot significantly affects performance; random or median-of-three selection helps avoid worst-case scenarios.

Time Complexity

O(n log n) avg, O(n²) worst

Space Complexity

O(log n)

def quick_sort(a):
  if len(a) <= 1: return a
  pivot = a[len(a)//2]
  left = [x for x in a if x < pivot]
  mid = [x for x in a if x == pivot]
  right = [x for x in a if x > pivot]
  return quick_sort(left) + mid + quick_sort(right)

Bubble Sort

Simple stable sort; repeatedly swap adjacent out-of-order elements. O(n^2).

How it works

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. It's simple to understand and implement, making it great for learning. However, it's inefficient for large datasets due to its quadratic time complexity. It's stable and works well on nearly-sorted data.

Time Complexity

O(n²)

Space Complexity

O(1)

def bubble_sort(a):
  n = len(a)
  for i in range(n):
    for j in range(n - i - 1):
      if a[j] > a[j+1]:
        a[j], a[j+1] = a[j+1], a[j]