Back to solutions

Sort an Array

MediumArrays

Sort an array ascending in O(n log n) without a library sort.

Open problem
Constraints
  • 1 <= n <= 5*10^4
  • -5*10^4 <= nums[i] <= 5*10^4

Merge sort

Time O(n log n)Space O(n)

Divide the array into halves, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element. Merging is linear and the recursion has log n levels, giving O(n log n) overall with guaranteed worst-case performance.

Key terms
divide and conquer:
Split the problem into smaller subproblems, solve them, and combine the results.
merge:
Combine two already-sorted lists into one sorted list in linear time.
void mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m, tmp); mergeSort(a, m, r, tmp);
    int i = l, j = m, k = l;
    while (i < m && j < r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < m) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int x = l; x < r; x++) a[x] = tmp[x];
}
Step by step
  1. If the range has 0 or 1 elements, it is already sorted.
  2. Split at the midpoint and sort each half recursively.
  3. Merge the two sorted halves by comparing front elements and copying the smaller.
  4. Copy the merged result back into the original range.