Explain why merge sort is O(n log n) in every case, and what its memory cost is.

Merge sort splits the list in half until single items remain. That takes about log2 n levels. At every level the merges together touch all n items once, so each level costs O(n). That gives n times log n, and it holds for any input order because the splitting and merging do not depend on the data. Merging needs a temporary array, so extra memory is O(n), plus O(log n) for the recursion stack. Merge sort is stable.

Find the k-th largest element of an unsorted array. Can you do better than sorting?

Use quickselect. Partition the array around a pivot so smaller values are on one side and larger on the other. The pivot ends at its final sorted position. If that position is the one you want, return it. Otherwise recurse into only the side that contains the position. Each round throws away part of the array, so the work is about n + n/2 + n/4 and so on, which is O(n) on average. A bad pivot every time gives O(n²), so pick a random or middle pivot. A min-heap of size k is an alternative with O(n log k) time that also works on streams.

Use the Master theorem to find the running time of T(n) = 3 T(n / 2) + n.

Here a = 3, b = 2 and the work outside the recursion is n, so d = 1. Compare a with b^d, which is 2. Since 3 is bigger than 2, the work grows towards the leaves of the recursion tree, so the bottom level dominates and T(n) = Θ(n^(log_2 3)), which is about n^1.58. This is the running time of Karatsuba multiplication.

Count the pairs in an array where an earlier element is larger than a later one, faster than O(n²).

Run merge sort and count while merging. Inversions inside each half are counted by the recursive calls. While merging, whenever the next item comes from the right half, it is smaller than every item still waiting in the left half, which are all earlier in the array, so add the number of left items remaining. The total is the sum of the two halves and the crossing count. Time is O(n log n) and memory is O(n).

Divide and Conquer

intermediate · 35 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

Divide and conquer has three steps. Divide the problem into smaller copies of itself, conquer each copy by recursion, then combine the answers.
Merge sort splits in half and merges in O(n), so it takes O(n log n) in every case. Quickselect keeps only one side, so it finds the k-th smallest in O(n) on average.
A recurrence such as T(n) = a T(n / b) + n^d describes the running time. Draw the recursion tree and see which level does the most work.
The Master theorem has three cases. Work is equal at every level, or the top level dominates, or the bottom level dominates.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use divide and conquer

Use divide and conquer when:

A problem can be split into smaller copies of itself, and the answers can be combined: sorting, searching, counting, multiplying big numbers.
The pieces are independent, so they can be solved separately, or even in parallel on different machines or cores.
You want to sort in O(n log n) in the worst case (merge sort), or find the k-th smallest or the median without sorting everything (quickselect).
You need to count something across a split, such as pairs that are out of order (inversions).

Use something else when:

The pieces overlap: the same smaller problem appears again and again, as in Fibonacci. Use dynamic programming to remember answers.
You only need the top k of a stream: a heap is simpler.
A simple loop does the job. Recursion adds overhead, so do not split a problem that one pass already solves.

Do not write your own sort in production. Every language ships an excellent one (see the real-world section). Write merge sort and quickselect to learn the pattern and for interviews.

How divide and conquer works

Divide and conquer has three steps:

Divide. Split the problem into smaller copies of the same problem.
Conquer. Solve each copy by recursion. A tiny copy (a base case) is solved directly.
Combine. Put the answers together.

The recursion tree is the whole story: count the work at each level, then add the levels up.

Two examples show the range:

Merge sort divides the list in half, sorts both halves, and combines by merging two sorted lists, which takes about n steps. There are log n levels and each level costs n, so the total is O(n log n) for any input.
Quickselect finds the k-th smallest by partitioning around a pivot, which puts the pivot in its final place. It then keeps only one side, the one that holds position k. The work shrinks as n + n/2 + n/4 + ..., which is O(n) on average.

To find the running time, write a recurrence: T(n) = a T(n / b) + n^d means "a subproblems, each 1/b the size, plus n^d work to split and combine". The Master theorem solves it by comparing a with b^d:

a equals b^d: every level does about the same work, so the total is Θ(n^d log n). Merge sort is 2, 2, 1, giving Θ(n log n).
a is bigger: the work grows towards the leaves, so the bottom level dominates and the total is Θ(n^(log_b a)). Karatsuba multiplication is 3, 2, 1, giving about Θ(n^1.58).
a is smaller: the work shrinks towards the leaves, so the top level dominates and the total is Θ(n^d). Quickselect on average is 1, 2, 1, giving Θ(n).

Try it

Pick one of the three techniques, then press Run and step through.

Divide and conquer

Step 1 of 15 · Press Space to play, arrow keys to step

Numbers to sort

Examples:

Numbers

Merge sort: split the list in half, sort each half the same way, then merge the two sorted halves. Splitting is free, and merging n items takes about n steps.

comparisons:: 0
merges:: 0
n × log2 n (upper bound):: 24

Divide and conquer splits a problem, solves the pieces, and combines the answers. The counters show the work compared with sorting or checking everything.

Speed

Things to try:

Merge sort, "Eight numbers": 5 2 9 1 7 3 8 4 is sorted with 17 comparisons, below the bound of 8 × 3 = 24. Try "Already sorted": it still splits and merges every level, using 12 comparisons.
Quickselect, "3rd smallest": 7 10 4 3 20 15 finds 7 after 2 partitions and looking at 10 items, where sorting would need about 18. For "Median of nine" it takes 2 partitions and looks at 15 items, against about 36 for a sort.
Master theorem, "Merge sort: 2 2 1" with n = 32: all 6 levels do 32 work, 192 in total. Switch to "Karatsuba: 3 2 1": the levels grow from 32 up to 243 and the bottom dominates. "Quickselect average: 1 2 1" shrinks from 32 to 1, a total of 63, about 2n.

Divide and conquer operations

Merge sort.

If the range has one item or none, it is sorted. Stop.
Find the middle. Sort the left half and the right half recursively.
Merge: compare the front items of both halves, take the smaller, and repeat. Copy what is left.

Quickselect (k-th smallest).

Pick a pivot, ideally random or the middle item, and partition: smaller items to the left, the rest to the right.
The pivot is now at its final position p. If p equals k - 1, return it.
If p is smaller than k - 1, repeat on the right side. Otherwise repeat on the left side.

Solve a recurrence.

Read off a (how many subproblems), b (how much smaller each is) and d (the power of n in the extra work).
Compare a with b^d and pick the case above.

Interview fact. Counting inversions is merge sort with one extra line: when an item from the right half is placed before the items still waiting in the left half, add the number of those left items to the count. It runs in O(n log n) instead of O(n²).

Divide and conquer time complexity

Algorithm	Best	Average	Worst	Extra memory
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n) for the recursion
Quickselect	O(n)	O(n)	O(n²)	O(1) after a copy
Binary search	O(1)	O(log n)	O(log n)	O(1) loop, O(log n) recursive

The worst case of quicksort and quickselect happens when the pivot is always the smallest or biggest item, for example the first item of already sorted data. A random or middle pivot makes that very unlikely.

Divide and conquer vs other approaches

n is the number of items and k is the position you want.

What you need	Divide and conquer	Sort first	Heap	Dynamic programming
Sort with a guaranteed O(n log n)	Merge sort	Not applicable	Heap sort, O(n log n)	Not applicable
The k-th smallest of an array	Quickselect, O(n) average	O(n log n)	O(n log k)	Not applicable
The top k of a stream	Not suitable	Not suitable	O(n log k)	Not applicable
Subproblems that overlap	Repeats work	Not applicable	Not applicable	Remembers answers
Work that can run in parallel	Pieces are independent	Hard to parallelise	Hard to parallelise	Often dependent

The bold cells show where each wins. Divide and conquer wins when the pieces are independent. It loses when the pieces overlap.

How to explain divide and conquer in an interview

Name the three steps out loud: divide, conquer, combine. Say what the combine step does.
Write the recurrence and say what each part means: "two halves, plus a linear merge".
Solve it with a recursion tree: "log n levels, n work per level".
For quickselect and quicksort, say the worst case and the fix: "a bad pivot gives O(n²), so I use a random pivot".
State both costs: merge sort is O(n log n) time and O(n) extra memory. Quickselect is O(n) average time and O(1) extra memory.

Where you meet divide and conquer in real systems

Divide and conquer is behind the sorting in your language, the way big data is processed across many machines, and how very large numbers are multiplied. Three examples are drawn out below, the first with code you can run, then more.

Example 1: Comparing two rankings, and finding a median

A search team wants to know how different two rankings of the same results are. The number of inversions, pairs that appear in opposite order, measures that, and merge sort counts them in O(n log n) instead of checking every pair. A monitoring job also needs the median response time of millions of requests, and quickselect finds it without sorting them all. Open the example below to see the picture and the code.

Code: count inversions with merge sort, and find the k-th smallestTime O(n log n) and O(n) averageMemory O(n)

Ranking A is the reference order 1 to 5. Ranking B puts the results in the order 2, 4, 1, 3, 5. Three pairs appear in opposite order: (2, 1), (4, 1) and (4, 3), so there are 3 inversions.

Run on the ranking 2 4 1 3 5, all five versions report 3 inversions. Run on 7 10 4 3 20 15 with k = 3, all five return 7 as the 3rd smallest. In practice you would call the library routine: C++ has std::nth_element, and Rust has select_nth_unstable. The C++ code builds with -std=c++17.

def count_inversions(values):
    """Count the pairs that are out of order: i < j but values[i] > values[j].

    Divide and conquer, the merge sort way: split the list in half, count the
    inversions inside each half, then count the ones that cross the middle while
    merging the two sorted halves. When the left item is bigger than the right one,
    it is also bigger than every item still waiting in the left half.

    Time:   O(n log n). log n levels of splitting, and each level does O(n) merging.
    Memory: O(n). The merged copies, plus O(log n) for the recursion.
    """
    def sort(items):
        if len(items) <= 1:
            return items, 0
        mid = len(items) // 2
        left, a = sort(items[:mid])                 # divide: solve each half
        right, b = sort(items[mid:])
        merged, crossing = [], 0
        i = j = 0
        while i < len(left) and j < len(right):     # combine: merge the sorted halves
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                crossing += len(left) - i           # right[j] is smaller than all remaining left items
                j += 1
        merged += left[i:] + right[j:]
        return merged, a + b + crossing

    return sort(list(values))[1]


def quickselect(values, k):
    """Return the k-th smallest value (k = 1 is the smallest) without sorting everything.

    Partition around a pivot so smaller values are on the left and bigger on the right.
    The pivot lands in its final sorted place. If that place is k - 1 we are done,
    otherwise keep only the side that holds position k - 1 and repeat on it.

    Time:   O(n) on average (the work shrinks as n + n/2 + n/4 ...), O(n^2) in the worst
            case when pivots are always the smallest or biggest value.
    Memory: O(n) for the copy, O(1) extra after that.
    """
    items = list(values)
    lo, hi = 0, len(items) - 1
    target = k - 1
    while True:
        mid = (lo + hi) // 2                        # a middle pivot avoids the worst case on sorted data
        items[mid], items[hi] = items[hi], items[mid]
        pivot, store = items[hi], lo
        for i in range(lo, hi):
            if items[i] < pivot:
                items[i], items[store] = items[store], items[i]
                store += 1
        items[store], items[hi] = items[hi], items[store]   # the pivot is now in its final place
        if store == target:
            return items[store]
        if store < target:
            lo = store + 1                          # the answer is in the right part
        else:
            hi = store - 1                          # the answer is in the left part

Example 2: Sorting a file bigger than memory

A database must sort a file that does not fit in memory. It reads a chunk that does fit, sorts it, writes it out as a sorted run, and repeats. Then it merges the sorted runs, reading the front of each run in turn. This is merge sort with the "split" done by chunk size, and it is how large sorts work in databases and big-data tools.

Each chunk is small enough to sort in memory. The merge step then only needs the front of each sorted run in memory at a time, so the whole file can be sorted without holding it all.

Example 3: Multiplying very large numbers

Schoolbook multiplication of two n-digit numbers takes about n² steps. Karatsuba multiplication splits each number in half and, with a clever rearrangement, needs only three half-size multiplications instead of four. Its recurrence is T(n) = 3 T(n / 2) + n, which gives about n^1.58. Python's big integers and Java's BigInteger use Karatsuba for large operands.

Two n-digit numbers are each split in half. Three multiplications of half-size numbers, plus some additions, give the full product. Fewer multiplications at each level means less work overall.

More real-world scenarios

4. MapReduce and distributed data processing

Frameworks such as MapReduce and Spark split data across many machines, process each part independently, and combine the results. The split, process and combine steps are divide and conquer at cluster scale.

5. Standard library sorts

Many standard libraries use merge-based sorting. Python's sort is Timsort, a merge sort that also takes advantage of runs already in order, and Java sorts objects with a similar algorithm. Merge sort is chosen because it is stable and its worst case is O(n log n).

6. Fast Fourier transform

The FFT, used in audio, image and signal processing, is a divide-and-conquer algorithm. It turns an O(n²) calculation into O(n log n) by splitting the input into even and odd positions.

7. Closest pair of points

Finding the two closest points among n points on a map can be done in O(n log n) by splitting the points in half by position, solving each half, and checking a thin strip along the dividing line.

8. Database sort-merge joins

A sort-merge join sorts both tables by the join key and then walks them together, which is the merge step of merge sort used to match rows.

9. Quicksort and introsort in libraries

C++'s std::sort is typically implemented with introsort, which uses quicksort and switches to heap sort if the recursion gets too deep, to avoid quicksort's O(n²) worst case.

10. Spatial subdivision

Graphics and game engines recursively split a scene or an image into quarters (a quadtree) to find nearby objects quickly. Each region is handled separately, and only regions that matter are searched.

Language standard libraries

You will almost always call the library instead of writing these.

Language	Structure or class	What it is under the hood	Notes
Java	`Arrays.sort`, `Collections.sort`	A merge-based sort for objects, a dual-pivot quicksort for primitives	Sorting objects is stable. There is no built-in quickselect, so use a `PriorityQueue` for top-k.
C++	`std::sort`, `std::stable_sort`, `std::nth_element`	Introsort-style sort, merge-based stable sort, a selection algorithm	`nth_element` is quickselect: it puts the k-th item in place in O(n) on average.
C#	`Array.Sort`, `List<T>.Sort`, LINQ `OrderBy`	An introspective sort; `OrderBy` is stable	There is no `nth_element`. Sort or keep a priority queue.
Rust	`slice::sort`, `sort_unstable`, `select_nth_unstable`	A stable merge-based sort, an unstable quicksort-style sort, a selection routine	`select_nth_unstable` finds the k-th item without sorting everything.
Python	`list.sort`, `sorted`, `heapq.nsmallest`	Timsort (merge-based, stable), a heap	There is no quickselect. `heapq.nsmallest(k, items)` is the usual choice for small `k`.
Go	`sort.Slice`, `slices.Sort`, `sort.Stable`	Pattern-defeating quicksort, a stable merge-based sort	The standard library has no selection routine.
JavaScript	`Array.prototype.sort`	An engine-defined sort, stable in modern engines	The comparison function must return a number. The default sort compares as strings.
Kotlin	`sorted()`, `sortedBy`	The JVM sort	The same behaviour as Java.

The pattern: sorting is solved for you in every language. Selection of the k-th item is built in only in C++ and Rust, so elsewhere you use a heap or write quickselect yourself.

The takeaway

Whenever a problem splits into independent smaller copies of itself, look for divide and conquer, and use the recursion tree to find its cost. When the copies overlap, it usually uses dynamic programming instead, and when only the top few items matter, a heap.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Explain why merge sort is O(n log n) in every case, and what its memory cost is.
easy
2.
Find the k-th largest element of an unsorted array. Can you do better than sorting?
medium
3.
Use the Master theorem to find the running time of T(n) = 3 T(n / 2) + n.
medium
4.
Count the pairs in an array where an earlier element is larger than a later one, faster than O(n²).
hard

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Sorting and Binary Search

Trees

Topics:Divide and conquerMerge sortQuickselectMaster theoremRecurrenceRecursion treeKth smallest