Sort an Array

medium array sorting merge sort

Problem

Sort the given integer array in ascending order without using built-in sort. Aim for O(n log n) time and the smallest possible space overhead.

Inputnums = [5,2,3,1]

Output[1,2,3,5]

Classic merge sort: split → sort halves → merge.

nums (comma-separated)

def sortArray(nums):
    def merge_sort(lo, hi):
        if hi - lo <= 1: return
        mid = (lo + hi) // 2
        merge_sort(lo, mid); merge_sort(mid, hi)
        merged = []
        i, j = lo, mid
        while i < mid and j < hi:
            if nums[i] <= nums[j]: merged.append(nums[i]); i += 1
            else: merged.append(nums[j]); j += 1
        merged.extend(nums[i:mid]); merged.extend(nums[j:hi])
        nums[lo:hi] = merged
    merge_sort(0, len(nums))
    return nums

function sortArray(nums) {
  function mergeSort(lo, hi) {
    if (hi - lo <= 1) return;
    const mid = (lo + hi) >> 1;
    mergeSort(lo, mid); mergeSort(mid, hi);
    const merged = [];
    let i = lo, j = mid;
    while (i < mid && j < hi) {
      if (nums[i] <= nums[j]) merged.push(nums[i++]);
      else merged.push(nums[j++]);
    }
    while (i < mid) merged.push(nums[i++]);
    while (j < hi) merged.push(nums[j++]);
    for (let k = 0; k < merged.length; k++) nums[lo + k] = merged[k];
  }
  mergeSort(0, nums.length);
  return nums;
}

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length);
        return nums;
    }
    void mergeSort(int[] a, int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) >>> 1;
        mergeSort(a, lo, mid); mergeSort(a, mid, hi);
        int[] merged = new int[hi - lo];
        int i = lo, j = mid, k = 0;
        while (i < mid && j < hi) merged[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i < mid) merged[k++] = a[i++];
        while (j < hi) merged[k++] = a[j++];
        for (k = 0; k < merged.length; k++) a[lo + k] = merged[k];
    }
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(a, lo, mid); mergeSort(a, mid, hi);
    vector<int> merged; merged.reserve(hi - lo);
    int i = lo, j = mid;
    while (i < mid && j < hi) merged.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i < mid) merged.push_back(a[i++]);
    while (j < hi) merged.push_back(a[j++]);
    for (int k = 0; k < (int)merged.size(); k++) a[lo + k] = merged[k];
}
vector<int> sortArray(vector<int>& nums) {
    mergeSort(nums, 0, (int)nums.size());
    return nums;
}

Explanation

We sort without the built-in function using merge sort, a classic divide and conquer method. The big idea: a tiny array is easy to sort, and two already-sorted pieces are easy to combine.

The helper merge_sort(lo, hi) works on the slice from lo up to (but not including) hi. If that slice has one element or fewer, it is already sorted and we stop. Otherwise we split at the middle and recursively sort the left and right halves.

Once both halves are sorted, we merge them. Two cursors i and j walk the two halves, and at each step we copy the smaller front value into merged. When one side runs out, we append whatever is left of the other. Finally we write merged back into the original slice.

Because each level of splitting does O(n) work merging and there are about log n levels, the total time is O(n log n).

Example: [5,2,3,1] splits into [5,2] and [3,1]. Those sort to [2,5] and [1,3]. Merging compares fronts (1 vs 2, then 2 vs 3, ...) to produce [1,2,3,5].

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