Merge Sort and Divide and Conquer

Merge sort algorithm

1. Divide: split the array into two halves
2. Conquer: recursively sort both halves
3. Combine: merge the two sorted halves

Merge sort implementation · merge

// Merge two sorted subarrays arr[left...mid] and arr[mid+1...right]
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // Size of left subarray
    int n2 = right - mid;      // Size of right subarray

    // Create temporary arrays
    vector<int> L(n1), R(n2);

    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back
    int i = 0;     // Initial index of left subarray
    int j = 0;     // Initial index of right subarray
    int k = left;  // Initial index of merged array

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Copy both halves out, then always take the smaller front. The two loops at the end copy whatever is left of one half.

Merge sort implementation · the recursion

// Main merge sort function
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

Merge sort implementation · main

void printArray(vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    cout << "Original array: ";
    printArray(arr);

    mergeSort(arr, 0, arr.size() - 1);

    cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}

Original array: 38 27 43 3 9 82 10
Sorted array:   3 9 10 27 38 43 82

Merge sort visualization

Input: [38, 27, 43, 3, 9, 82, 10]

                    [38, 27, 43, 3, 9, 82, 10]
                    /                        \
           [38, 27, 43, 3]                [9, 82, 10]
           /            \                  /         \
      [38, 27]        [43, 3]          [9, 82]      [10]
      /     \         /     \          /     \
    [38]   [27]    [43]    [3]      [9]    [82]
      \     /         \     /          \     /
      [27, 38]        [3, 43]          [9, 82]      [10]
           \            /                  \         /
           [3, 27, 38, 43]                [9, 10, 82]
                    \                        /
                    [3, 9, 10, 27, 38, 43, 82]

Merge sort complexity

Merge sort characteristics

Advantages

• Guaranteed O(n log n) performance
• Stable: preserves the order of equal elements
• Predictable: always the same time complexity
• Good for linked lists: no random access needed

Disadvantages

• Extra space: requires O(n) additional memory
• Not in-place: uses auxiliary arrays
• Slower for small arrays: overhead of recursion

Another version · a global array

The same algorithm on a global array a, with the halves copied into local arrays L and R. main prints the array before and after sorting.

void merge(int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1];
    int R[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = a[l + i];
    }

    for (int i = 0; i < n2; i++) {
        R[i] = a[m + 1 + i];
    }

    int uk1 = 0;
    int uk2 = 0;
    int k = l;
    while (uk1 < n1 && uk2 < n2) {
        if (L[uk1] <= R[uk2]) {
            a[k] = L[uk1];
            uk1++;
        } else {
            a[k] = R[uk2];
            uk2++;
        }
        k++;
    }

    while (uk1 < n1) {
        a[k] = L[uk1];
        uk1++; k++;
    }
    while (uk2 < n2) {
        a[k] = R[uk2];   // fixed: was L[uk2] — the tail of the right half
        uk2++; k++;
    }

}

#include <iostream>

using namespace std;
int a[1000];

void merge(int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1];
    int R[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = a[l + i];
    }

    for (int i = 0; i < n2; i++) {
        R[i] = a[m + 1 + i];
    }

    int uk1 = 0;
    int uk2 = 0;
    int k = l;
    while (uk1 < n1 && uk2 < n2) {
        if (L[uk1] <= R[uk2]) {
            a[k] = L[uk1];
            uk1++;
        } else {
            a[k] = R[uk2];
            uk2++;
        }
        k++;
    }

    while (uk1 < n1) {
        a[k] = L[uk1];
        uk1++; k++;
    }
    while (uk2 < n2) {
        a[k] = R[uk2];   // fixed: was L[uk2] — the tail of the right half
        uk2++; k++;
    }

}

void mergesort(int l, int r) {
    if (l < r ) {
        int m = (l + r) / 2;
        mergesort(l, m);
        mergesort(m + 1, r);
        merge(l, m, r);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;    
    mergesort(0, n - 1);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

7
10 13 43 1 534 3 48

10 13 43 1 534 3 48
1 3 10 13 43 48 534

Another version · strict comparison

The same program with if (L[uk1] < R[uk2]). On equal values it now takes from the right half first — still sorted, but no longer stable. For plain numbers you cannot see the difference; for records sorted by one field you can.

#include <iostream>

using namespace std;
int a[1000];

void merge(int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1];
    int R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = a[i + l];
    for (int i = 0; i < n2; i++)
        R[i] = a[i + m + 1];

    int uk1 = 0;
    int uk2 = 0;
    int k = l;
    while (uk1 < n1 && uk2 < n2) {
        if (L[uk1] < R[uk2]) {
            a[k] = L[uk1];
            uk1++;
        } else {
            a[k] = R[uk2];
            uk2++;
        }
        k++;
    }
    while (uk1 < n1) {
        a[k] = L[uk1];
        uk1++; k++;
    }
    while (uk2 < n2) {
        a[k] = R[uk2];   // fixed: was L[uk2] — the tail of the right half
        uk2++; k++;
    }
}

void merge_sort(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(l, m);
        merge_sort(m + 1, r);
        merge(l, m, r);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    merge_sort(0, n - 1);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

7
10 13 43 1 534 3 48

1 3 10 13 43 48 534

Side by side

1 · Finding inversions in an array

Problem: count pairs (i, j) where i < j but arr[i] > arr[j].
Solution: a modified merge sort counts inversions during the merge.

long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    long long inv_count = 0;

    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            // All remaining elements in L are greater than R[j]
            inv_count += (L.size() - i);
        }
    }

    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];

    return inv_count;
}

long long countInversions(vector<int>& arr, int left, int right) {
    long long inv_count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        inv_count += countInversions(arr, left, mid);
        inv_count += countInversions(arr, mid + 1, right);
        inv_count += mergeAndCount(arr, left, mid, right);
    }
    return inv_count;
}

// Example: [8, 4, 2, 1]
// Inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) = 6

Check: [8, 4, 2, 1] gives 6 — every pair is an inversion. [2, 4, 1, 3, 5] gives 3: (2,1), (4,1), (4,3).

2 · Finding the k-th smallest element

Problem: find the k-th smallest element without fully sorting.
Solution: quick select — a modified quick sort that recurses into one side only.

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int quickSelect(vector<int>& arr, int low, int high, int k) {
    if (low <= high) {
        int pi = partition(arr, low, high);

        if (pi == k)
            return arr[pi];
        else if (pi > k)
            return quickSelect(arr, low, pi - 1, k);
        else
            return quickSelect(arr, pi + 1, high, k);
    }
    return -1;
}

// Example: Find 3rd smallest in [7, 10, 4, 3, 20, 15]
// quickSelect(arr, 0, 5, 2) returns 7
// O(n) average time vs O(n log n) for sorting

k is a 0-based index here: quickSelect(arr, 0, 5, 2) on [7, 10, 4, 3, 20, 15] returns 7 — the 3rd smallest. This partition takes the last element as pivot, unlike the quick sort from the previous lecture.

3 · Closest pair of points

Problem: find the two closest points in a 2D plane.
Solution: divide and conquer, similar to merge sort.

struct Point {
    int x, y;
};

double distance(Point p1, Point p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

double closestPair(vector<Point>& points, int left, int right) {
    // Base case: brute force for small arrays
    if (right - left <= 3) {
        double minDist = INT_MAX;
        for (int i = left; i < right; i++)
            for (int j = i + 1; j <= right; j++)
                minDist = min(minDist, distance(points[i], points[j]));
        return minDist;
    }

    // Divide
    int mid = left + (right - left) / 2;
    double dl = closestPair(points, left, mid);
    double dr = closestPair(points, mid + 1, right);
    double d = min(dl, dr);

    // Check points near dividing line
    // ... (additional logic for strip)

    return d;
}

4 · Maximum subarray sum

Problem: find the contiguous subarray with the largest sum.
Solution: divide and conquer (Kadane's algorithm is simpler, but this shows the idea).

int maxCrossingSum(vector<int>& arr, int left, int mid, int right) {
    int sum = 0;
    int leftSum = INT_MIN;

    // Find max sum from mid to left
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum)
            leftSum = sum;
    }

    sum = 0;
    int rightSum = INT_MIN;

    // Find max sum from mid+1 to right
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > rightSum)
            rightSum = sum;
    }

    return leftSum + rightSum;
}

int maxSubarraySum(vector<int>& arr, int left, int right) {
    if (left == right)
        return arr[left];

    int mid = left + (right - left) / 2;

    return max({maxSubarraySum(arr, left, mid),
                maxSubarraySum(arr, mid + 1, right),
                maxCrossingSum(arr, left, mid, right)});
}

// Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// Result: 6 (subarray [4, -1, 2, 1])

For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the result is 6 — the subarray [4, -1, 2, 1].

5 · Binary search

Problem: search for an element in a sorted array.
Solution: divide and conquer.

int binarySearch(vector<int>& arr, int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;

        if (arr[mid] > target)
            return binarySearch(arr, left, mid - 1, target);

        return binarySearch(arr, mid + 1, right, target);
    }
    return -1;
}

On [2, 3, 4, 10, 40]: searching 10 returns index 3, searching 5 returns −1.

6 · Counting smaller elements to the right

Problem: for each element, count how many elements to its right are smaller.
Solution: a modified merge sort over (value, original index) pairs.

void mergeWithCount(vector<pair<int,int>>& arr, int left, int mid, int right,
                    vector<int>& count) {
    vector<pair<int,int>> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i].first <= arr[j].first) {
            // Elements from j to right are greater
            count[arr[i].second] += (j - mid - 1);
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        count[arr[i].second] += (right - mid);
        temp[k++] = arr[i++];
    }

    while (j <= right)
        temp[k++] = arr[j++];

    for (int i = 0; i < temp.size(); i++)
        arr[left + i] = temp[i];
}

When an element from the left half is placed, j − mid − 1 elements of the right half have already gone before it — exactly the smaller ones to its right. Call it from a usual merge-sort recursion; for [5, 2, 6, 1] the counts are 2 1 1 0.

Use bubble sort when

• The array is very small (< 10 elements)
• The array is nearly sorted
• Simplicity is more important than efficiency
• Teaching and learning

Use merge sort when

• Stability is required
• Guaranteed O(n log n) is needed
• Sorting linked lists
• External sorting (data does not fit in memory)
• Parallel processing (easily parallelizable)

Use quick sort when

• Average-case performance matters most
• Memory is limited (in-place sorting)
• Sorting arrays (not linked lists)
• Cache performance is important
• Data is randomly ordered

Eight things to remember

1. Bubble sort is O(n²) — too slow for large datasets
2. Merge sort guarantees O(n log n) but uses O(n) extra space
3. Quick sort is the fastest in practice but has an O(n²) worst case
4. Divide and conquer is powerful for many problems beyond sorting
5. Choose the algorithm by the requirements: stability, space, worst-case guarantees
6. Quick select finds the k-th element in O(n) average time
7. Inversion counting measures how sorted an array is
8. Both algorithms use recursion and the divide-and-conquer paradigm

Q1 · Why is quick sort faster than merge sort in practice?

Quick sort has better cache locality and fewer data movements. It partitions in place, while merge sort copies data to temporary arrays. The constant factors in O(n log n) are smaller for quick sort.

Q2 · When would merge sort be better than quick sort?

• Guaranteed O(n log n) performance — no O(n²) worst case
• Stable sorting — the order of equal elements is preserved
• Sorting linked lists — no random access needed
• External sorting — sorting data on disk

Q3 · Can we avoid quick sort's O(n²) worst case?

• Use random pivot selection
• Use median-of-three pivot selection
• Use introsort — switch to heap sort when the recursion gets too deep

Q4 · Why is finding inversions useful?

Inversions measure how unsorted an array is. Applications:

• Collaborative filtering (recommendation systems)
• Measuring similarity between rankings
• Detecting anomalies in data

Q5 · Is recursion necessary for these algorithms?

No — both can be written iteratively with an explicit stack, but the recursive versions are simpler and more intuitive.

Try these

1. Implement quick sort with random pivot selection
2. Count inversions in an array using merge sort
3. Find the k-th largest element using quick select
4. Sort an array of 0s, 1s and 2s (Dutch National Flag problem)
5. Merge k sorted arrays using the merge sort approach
6. Find the median of two sorted arrays
7. Count of smaller elements after self
8. Sort an array by increasing frequency

Problem to topic