Sort an Array — Editorial

Opening the reading…

Intuitionwhy dividing the array makes merging cheap

A sorted array is easy to build from two sorted arrays. Compare the first unused value from each half, take the smaller one, and repeat; once one half is empty, append the remainder of the other. Each value is examined and copied once during that merge, so combining two sorted halves costs linear time.

The unsorted array does not give you those sorted halves for free, so split it until every piece contains one value. A one-value piece is already sorted. Then merge neighboring pieces as the recursion returns: small sorted pieces become larger sorted pieces, and after log n levels the whole array is sorted. The same values are never compared across every possible pair, which is why the total work is O(n log n) instead of quadratic.

Splitting creates sorted pieces; merging does the useful linear work at every level.

Approachthe recursive merge sort plan

Start mergeSort on the entire index range and stop when left is at least right, because an empty or one-value range is already sorted and cannot be split usefully.

Compute mid as left + (right - left) / 2, because this finds the middle without risking overflow from adding two large indices.

Recursively sort the range from left through mid and the range from mid + 1 through right, because merge is correct only when both input ranges are already sorted.

Create a temporary array for the current range and compare the first unused value from each half, placing the smaller value next; without this choice, the merged result could not stay ascending.

Copy whichever half still has values after one side is exhausted, because those remaining values are already sorted and are all larger than the values just placed from that side.

Copy the temporary values back into nums starting at left, because the next larger merge must read the sorted result from the original array.

Return nums after the top-level range has been merged, because the required output is the input array in ascending order and the recursive calls modify it in place apart from temporary merge storage.

Complexitywhy every level costs linear time

MEASURE	BOUND	WHY
Time	O(n log n)	There are O(log n) split levels, and at each level every value is copied or compared as part of exactly one merge across the disjoint ranges. The work is therefore O(n) per level rather than repeated for overlapping subarrays.
Space	O(n) extra	The temporary array at the largest merge holds n values, and the recursion stack adds O(log n) frames. The returned array is required output and is excluded from extra space. The bound does not degrade for a particular input shape because the index ranges are always split nearly in half.

Here n is the array length and h is the recursion depth; merge sort keeps h at O(log n) for every input shape because it always splits index ranges in half.

Annotated solutionC++ - recursive merge sort with one temporary range

CPPDivide each range recursively, merge its sorted halves, and write the merged values back.

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        for (int p = 0; p < k; ++p) {
            nums[left + p] = temp[p];
        }
    }
};

The temporary array belongs only to the current merge, not to the whole recursion tree. The two recursive calls finish before merge reads either half, so nums[left..mid] and nums[mid + 1..right] are valid sorted inputs. The comparison uses <=, which keeps equal values in their original left-before-right order, although the problem only requires ascending values.

The heap sort alternativewhen constant extra space matters more than the simpler merge

Heap sort is a genuine space optimisation rather than a different time bound. It builds a max heap inside nums, repeatedly moves the largest value to the end, and restores the heap in the remaining prefix. The result is O(n log n) time and O(1) extra space, but the heap invariant takes more code and is usually less direct to debug than merge sort.

CPPBuild a max heap in place, then move its maximum to the array's final position.

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = static_cast<int>(nums.size());

        for (int i = n / 2 - 1; i >= 0; --i) {
            siftDown(nums, i, n);
        }

        for (int end = n - 1; end > 0; --end) {
            swapValues(nums[0], nums[end]);
            siftDown(nums, 0, end);
        }

        return nums;
    }

private:
    void siftDown(vector<int>& nums, int root, int size) {
        while (true) {
            int child = 2 * root + 1;
            if (child >= size) {
                return;
            }

            if (child + 1 < size && nums[child] < nums[child + 1]) {
                ++child;
            }

            if (nums[root] >= nums[child]) {
                return;
            }

            swapValues(nums[root], nums[child]);
            root = child;
        }
    }

    void swapValues(int& first, int& second) {
        int saved = first;
        first = second;
        second = saved;
    }
};