# Merge Sort and Quicksort

Two divide-and-conquer sorts: merge sort splits evenly and merges, quicksort partitions around a pivot and recurses.

**Rests on:** Dynamic Programming

*Machine Learning · Algorithms and Complexity*


## Why learn this

These two sorting methods are essential because they turn chaotic lists into ordered ones efficiently, a task you perform daily whether you realize it or not. Consider your phone’s contact list: when you type 'A', you expect the names starting with A to appear instantly at the top, not after a long delay while the system scans every other name. Or consider a large Excel spreadsheet; if you want to sort thousands of rows by date, you need an algorithm that finishes in seconds, not hours. These methods provide that speed and reliability for massive datasets, ensuring systems like search engines or financial databases remain responsive under heavy load.


## The intuition

Imagine you have a messy pile of exam papers that need to be sorted alphabetically. You could do it the slow way: pick a paper, scan the whole pile to find its correct position, insert it, and repeat. That's like a simple sort that's easy to write but gets painfully slow as the pile grows. Merge sort and quicksort are two smarter strategies based on a method called 'divide and conquer'—which simply means breaking a large problem into smaller, manageable pieces, solving each piece independently, and then combining the results.

Merge sort is like dividing the pile into two halves, sorting each half (by dividing again), and then merging the two sorted halves by comparing the top cards of each. It's methodical and guaranteed to work well. For example, if you have 100 papers, you split them into two piles of 50, sort those, and then combine. The time taken grows steadily as the pile gets bigger.

Quicksort is like picking a paper as a 'pivot,' then shuffling papers so all those alphabetically before the pivot go to one side, and all after go to the other. Then you sort each side independently using the same trick. It's usually faster in practice, but if you pick a bad pivot, it can become slow. Both methods end up with a perfectly sorted pile, but they get there differently.


## An analogy

Think of sorting a deck of cards. Merge sort is like a team of card players: split the deck into two halves, each player sorts their half (by splitting again), then you merge two sorted piles by repeatedly comparing the top card of each and placing the smaller one into a new pile. This always works, but you need extra table space for the new pile.

Quicksort is like sorting by a 'pivot' card: pick one card, then arrange all cards lower than the pivot to the left, all higher to the right. Now the pivot is in its final position. Repeat on the left and right sub-piles. It works in-place, using minimal extra space, but if your pivot is always the smallest or largest card, you end up with a one-card group each time, making it much slower. That's the key trade-off: merge sort is slow but steady, quicksort is fast but can have bad days.


## Definition

Merge sort is an algorithm that sorts a list by repeatedly splitting it into halves, sorting those halves, and merging them back together in order; quicksort sorts a list by picking a reference item, placing smaller items on one side and larger items on the other, and repeating this process for each side.


## How it connects

This topic builds on basic list operations and comparison — the ability to compare two numbers and move them. It sits within the 'Algorithms and Complexity' branch of your studies; you'll soon formalize its efficiency with Big-O notation, which describes how the time grows with input size.


## The mathematics

Both sorts belong to the branch of discrete mathematics concerned with counting operations — how many comparisons and moves are needed. We don't use calculus; we count steps. The key mathematical idea is a 'recurrence': the number of steps to sort n items is expressed in terms of the number of steps to sort smaller pieces. 

For merge sort: to sort n items, split into two halves. Sorting each half takes T(n/2) steps. Merging two sorted halves of size n/2 each takes about n steps (compare the front of each, pick the smaller). So total steps T(n) = 2*T(n/2) + n. Solving this gives T(n) = n log₂(n) – more precisely, the number of times you can double from 1 to n (the logarithm base 2). For quicksort, the recurrence depends on the pivot: if the pivot lands in the middle, same as merge sort: T(n) = 2*T(n/2) + n, so n log n. If the pivot is always the smallest, you get T(n) = T(n-1) + n, which sums to n²/2 — a quadratic explosion.

Merge sort recurrence: T(n) = 2T(n/2) + n, solving to T(n) = O(n log n). Quicksort average: T(n) = 2T(n/2) + O(n) = O(n log n); worst-case (bad pivot) T(n) = T(n-1) + O(n) = O(n²).


## A worked example

```
We'll sort the list [5, 2, 9, 1] using merge sort, then quicksort.

Step 1: Split: [5,2] and [9,1]   # Split the list into two halves.
Step 2: Split each half: [5], [2], [9], [1]   # Each single element is already sorted.
Step 3: Merge [5] and [2]: compare 5 and 2, take 2, then 5 → [2,5]   # Merge the two single-element lists.
Step 4: Merge [9] and [1]: compare 9 and 1, take 1, then 9 → [1,9]   # Merge the other pair.
Step 5: Merge [2,5] and [1,9]: compare 2 and 1, take 1; compare 2 and 9, take 2; compare 5 and 9, take 5; then 9 → [1,2,5,9]   # Compare the front elements of each sorted list, pick the smaller, until both are exhausted. Result is fully sorted.

Result: Sorted list: [1,2,5,9]. Total merges: log₂(4)=2 levels, each level does 4 comparisons, total 4*2=8 comparisons (roughly n log n).
```


## From scratch, in Python

```python
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
    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

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(merge_sort([5, 2, 9, 1]))
print(quicksort([5, 2, 9, 1]))
```


## What the code does

The code defines two functions. `merge_sort` checks if the list has one or zero elements — that's sorted. Otherwise it finds the middle index (`mid`), slices the list into left and right halves, recursively sorts each, and merges the results. The `merge` function compares the first elements of `left` and `right`, appends the smaller to `result`, and continues. After one list is exhausted, it extends with the remainder. 

`quicksort` picks a pivot (the middle element). It uses list comprehensions to create `left` (all elements less than pivot), `middle` (equal to pivot), and `right` (greater). It recursively sorts left and right, then concatenates. The base case is the same. 

In Python, lists are indexed from 0, and slicing `arr[:mid]` gives elements from start to mid-1. The `while` loop continues as long as both lists have elements. `extend` adds all elements from another list to the end.


## Common misconceptions

**Merge sort is always faster than quicksort** — Merge sort has guaranteed n log n time, so it must be faster than quicksort which can be n².

Quicksort's average case is also n log n, and in practice it has much lower constant factors and better cache locality, so it usually wins. Merge sort's extra space allocation and copying add overhead. In fact: Quicksort is typically faster in practice due to smaller constants, despite the same asymptotic average. Merge sort's guarantee matters when worst-case is unacceptable.

**Quicksort always picks the middle element** — The standard implementation always uses the middle element as pivot.

Pivot can be first, last, random, or median-of-three. The choice greatly affects performance. In fact: Pivot selection is a design choice; random or median-of-three is common to avoid worst-case on sorted input.

**Both sorts need extra memory** — Merge sort and quicksort both require O(n) extra space.

Quicksort can be implemented in-place with O(log n) stack space, whereas merge sort naively requires O(n) auxiliary array. In-place merge sorts exist but are complex. In fact: Merge sort needs O(n) extra space; quicksort can use O(log n) space for recursion and can sort in place.

**Sorting a small list is the same as sorting a large one** — The algorithm's efficiency doesn't matter for small lists; it's always fast.

For small lists, the overhead of recursion and function calls may dominate; simple insertion sort can be faster for n < 10. In fact: Many libraries use a hybrid: quicksort for large, insertion sort for small, to reduce overhead.

**Stability doesn't matter** — Stability is a minor detail; any sort is fine as long as it outputs sorted order.

When sorting by multiple keys, stability preserves the order of earlier keys when later keys are equal. This is essential in many applications like database sorting. In fact: A stable sort is required when you sort by one attribute and then by another; merge sort is stable, quicksort is not typically.


## In short

Both sorts use divide and conquer. Merge sort splits evenly, recurses, and merges, giving guaranteed n log n time but needing extra space. Quicksort partitions around a pivot and recurses, typically faster but with a worst-case quadratic risk depending on pivot choice. Know the trade-offs: merge sort for stability and guaranteed performance, quicksort for in-place speed.


## Where this is used

Merge sort is the default for sorting in many standard libraries because it is stable (preserves order of equal elements) and guarantees n log n time. Quicksort is the in-place sort used in practice; for example, GNU's C++ `std::sort` uses introsort, which starts with quicksort and falls back to heapsort if recursion depth gets too deep, to avoid the quadratic worst case. 

In large language models, sorting is used to rank token outputs by probability during beam search — the decoder keeps the top-scoring sequences, which requires a priority queue (often built on a heap, not a sort, but sorting comes in when candidates are collected). In retrieval-augmented generation (RAG), embedding vectors are compared and the top-k most similar documents must be sorted by similarity score; many vector databases use approximate nearest neighbour (ANN) indexes that sort and partition data. 

For small models on phones, sorting is used in keyboard applications for next-word prediction and in speech recognition to reorder candidate transcriptions by likelihood. 

In agentic systems, planning involves sorting actions by estimated value or cost, and tool selection often ranks tools. Everyday machine learning, like fraud detection, sorts transactions by anomaly score to prioritize review. 

A developer writing an application that needs to sort a list in Python simply calls `sorted(my_list)` or `list.sort()`, and the underlying engine chooses the optimal algorithm. If you need a stable sort, `sorted` is guaranteed stable. If you're implementing a custom data structure, you might write your own quicksort — but the key is to know the trade-offs you're inheriting.


---

Read this on the web: https://basavapurushottam.com/learn-ai/merge-sort-and-quicksort
