Learn DSA Part 8: Sorting and Binary Search - Merge Sort, Quick Sort and Binary Search on Answer

Sorting and binary search go together: sorting puts data in order, and binary search exploits that order to find things in O(log n) instead of O(n). Interviewers ask about both, from "explain how merge sort works" to the very popular "binary search on the answer" problems that do not even look like search at first.

This is Part 8 of the Learn DSA series. We compare the main sorting algorithms, write merge sort, cover quick sort and quickselect, explain how library sorts behave in C++ and Java, and finish with a bug-free binary search template and its most useful variations. Code is in C++ and Java.

1. Sorting algorithms at a glance

A stable sort keeps equal elements in their original relative order, which matters when you sort records by one key after another. Comparison-based sorts cannot beat O(n log n) in the worst case; counting and radix sort get around this only when keys are small integers in a range of size k.

Insertion sort is still useful: it is very fast on small or nearly sorted arrays, which is why real library sorts switch to it for tiny subarrays.

2. Merge sort: divide and conquer

Split the array in half, sort each half recursively, then merge the two sorted halves in linear time. The recurrence is T(n) = 2T(n/2) + O(n), which gives O(n log n) in every case (Part 1). The cost is O(n) extra memory for merging.

// Merge sort: O(n log n) time, O(n) extra space, stable
void mergeSort(vector<int>& a, int lo, int hi, vector<int>& tmp) {
    if (hi - lo < 1) return;                 // 0 or 1 element
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid + 1, hi, tmp);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
// call: vector<int> tmp(a.size()); mergeSort(a, 0, a.size() - 1, tmp);

// Merge sort: O(n log n) time, O(n) extra space, stable
static void mergeSort(int[] a, int lo, int hi, int[] tmp) {
    if (hi - lo < 1) return;                 // 0 or 1 element
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid + 1, hi, tmp);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
// call: mergeSort(a, 0, a.length - 1, new int[a.length]);

The merge step is useful on its own: counting inversions, merging k sorted lists and sorting linked lists (where merge sort needs no extra array) are all variations.

3. Quick sort and quickselect

Quick sort picks a pivot, partitions the array so smaller elements go left and larger ones go right, then sorts both sides recursively. It sorts in place and is very fast in practice, but a bad pivot every time (for example, always the first element of an already sorted array) degrades it to O(n^2). Choosing a random pivot makes that worst case extremely unlikely.

Quickselect uses the same partition step but recurses into only one side, finding the k-th smallest element in O(n) average time. It is the classic answer to "Kth Largest Element in an Array", alongside the heap approach from Part 10.

4. Library sorts and custom comparators

• C++ sort uses introsort (quick sort that falls back to heap sort, with insertion sort for small ranges): O(n log n) worst case, not stable. Use stable_sort when order of equal elements matters.
• Java Arrays.sort uses dual-pivot quick sort for primitive arrays (not stable) and TimSort for objects and Collections.sort (stable, O(n log n)).
• Custom order: pass a comparator, for example sorting intervals by start time or strings by length. In C++ the comparator must return true only when a should come strictly before b; returning true for equal elements is undefined behaviour.

5. A bug-free binary search template

Binary search keeps a range [lo, hi] that is guaranteed to contain the answer and halves it every step, so it takes O(log n) steps. The safest general form finds the first index where a condition becomes true (also called lower bound):

// First index i with a[i] >= target (a.size() if none). O(log n)
int lowerBound(const vector<int>& a, int target) {
    int lo = 0, hi = a.size();               // answer is in [lo, hi]
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;      // condition true: go left
        else lo = mid + 1;                   // condition false: go right
    }
    return lo;
}

// First index i with a[i] >= target (a.length if none). O(log n)
static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;               // answer is in [lo, hi]
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;      // condition true: go left
        else lo = mid + 1;                   // condition false: go right
    }
    return lo;
}

Two details prevent most bugs: compute the middle as lo + (hi - lo) / 2 to avoid integer overflow, and make sure the range always shrinks (here hi = mid or lo = mid + 1). Finding the first and last position of a value, the insert position, and searching a rotated sorted array are all variations of this template.

6. Binary search on the answer

Many problems ask for the minimum (or maximum) value that satisfies a condition, such as "the slowest eating speed that finishes all bananas in h hours" or "the smallest ship capacity that delivers all packages in d days". If the condition is monotonic (once a value works, every larger value also works), you can binary search over the possible answers and test each candidate with a greedy check.

// Koko Eating Bananas: minimum speed to finish all piles within h hours
bool canFinish(const vector<int>& piles, long long speed, long long h) {
    long long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;   // ceil(p / speed)
    return hours <= h;
}
int minEatingSpeed(const vector<int>& piles, int h) {
    long long lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) hi = mid;   // works: try slower
        else lo = mid + 1;                        // too slow: go faster
    }
    return (int)lo;
}

// Koko Eating Bananas: minimum speed to finish all piles within h hours
static boolean canFinish(int[] piles, long speed, long h) {
    long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;   // ceil(p / speed)
    return hours <= h;
}
static int minEatingSpeed(int[] piles, int h) {
    long lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) hi = mid;   // works: try slower
        else lo = mid + 1;                        // too slow: go faster
    }
    return (int) lo;
}

The total cost is O(n log M), where M is the size of the answer range. Recognising this pattern ("minimise the maximum", "smallest value such that") is one of the most valuable interview skills in this series.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. For binary search problems, write down the condition you are searching on before coding.

1. Binary Search (easy)
2. Search Insert Position (easy)
3. First Bad Version (easy)
4. Sort Colors (medium)
5. Find First and Last Position of Element in Sorted Array (medium)
6. Search in Rotated Sorted Array (medium)
7. Find Minimum in Rotated Sorted Array (medium)
8. Kth Largest Element in an Array (medium, quickselect or heap)
9. Merge Intervals (medium, sort first)
10. Koko Eating Bananas (medium, binary search on answer)
11. Capacity To Ship Packages Within D Days (medium)
12. Sort an Array (medium, implement merge sort)
13. Split Array Largest Sum (hard)
14. Median of Two Sorted Arrays (hard)