Sorting Algorithms

Quick Reference

Interview rule: In Python, always use sorted() or .sort() — it's Timsort, the best practical sort. Only implement manually if the interviewer asks.

---

Python Built-in Sorting

# sorted() — returns new list, works on any iterable
nums = [4, 1, 7, 3]
sorted_nums = sorted(nums)                        # [1, 3, 4, 7]
sorted_desc = sorted(nums, reverse=True)          # [7, 4, 3, 1]

# .sort() — in-place, only for lists
nums.sort()
nums.sort(key=lambda x: -x)                       # sort descending

# Sort by custom key
people = [("Alice", 30), ("Bob", 25), ("Eve", 35)]
sorted(people, key=lambda x: x[1])               # by age
sorted(people, key=lambda x: (-x[1], x[0]))      # age desc, name asc

---

Bubble Sort — O(n²)

Simple comparison-based sort. Repeatedly swaps adjacent elements.

def bubble_sort(arr):
    n = len(arr)
    while True:
        swapped = False
        for i in range(1, n):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                swapped = True
        n -= 1
        if not swapped:
            break
    return arr

---

Insertion Sort — O(n²)

Builds sorted array one element at a time. Efficient for small/nearly-sorted input.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j - 1] > arr[j]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1
    return arr

---

Merge Sort — O(n log n)

Divide and conquer. Stable. Guaranteed O(n log n) but uses O(n) space.

def merge_sort(arr):
    if len(arr) < 2:
        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
    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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

Quick Sort — O(n log n) avg

Divide and conquer with in-place partitioning. Fast in practice but O(n²) worst case.

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

---

Heap Sort — O(n log n), O(1) space

Uses a max-heap. Guaranteed O(n log n) with O(1) space. Not stable.

import heapq

def heap_sort(arr):
    # Python heapq is min-heap — negate for max-heap behaviour
    min_heap = arr[:]
    heapq.heapify(min_heap)
    return [heapq.heappop(min_heap) for _ in range(len(min_heap))]

# In-place heap sort using max-heap
def heap_sort_inplace(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]: largest = left
    if right < n and arr[right] > arr[largest]: largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

---

Interview Tips

• Always ask: "Can I use Python's built-in sort?" — almost always yes
• Merge sort → when you need stable sort or guaranteed O(n log n)
• Quick sort → when average performance matters and space is tight
• Counting sort / Radix sort → when input is bounded integers (O(n+k))
• Sorting is often a pre-processing step — sort first, then apply binary search or two pointers