29. Sort an Array · DSA Practice

Sort nums in ascending order without built-in sort functions, in O(n log n) time. (Implement merge sort, heap sort or a randomised quick sort.)

Example 1

Input: nums = [5,2,3,1]

Output: [1,2,3,5]

Example 2

Input: nums = [5,1,1,2,0,0]

Output: [0,0,1,1,2,5]

Hint 1

Split in half, sort each half recursively, then merge two sorted lists in linear time.

SortingDivide and Conquer

Approach 1: Bubble / insertion sort

Simple but quadratic: too slow for 5·10⁴ elements.

⏱ Time O(n²)💾 Space O(1)

Approach 2: Merge sort ✅

Divide and conquer with a linear merge; stable and always O(n log n).

⏱ Time O(n log n)💾 Space O(n)

Reference solution for Merge sort (time O(n log n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])      # divide
        right = self.sortArray(nums[mid:])
        res, i, j = [], 0, 0
        while i < len(left) and j < len(right):  # conquer: merge two sorted halves
            if left[i] <= right[j]:
                res.append(left[i]); i += 1
            else:
                res.append(right[j]); j += 1
        return res + left[i:] + right[j:]

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        return nums;
    }
    private void mergeSort(int[] a, int[] tmp, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSort(a, tmp, lo, mid);
        mergeSort(a, tmp, mid + 1, hi);
        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];
    }
}

class Solution {
    void mergeSort(vector<int>& a, vector<int>& tmp, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSort(a, tmp, lo, mid);
        mergeSort(a, tmp, mid + 1, hi);
        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];
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mergeSort(nums, tmp, 0, (int)nums.size() - 1);
        return nums;
    }
};

function sortArray(nums) {
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  const left = sortArray(nums.slice(0, mid)), right = sortArray(nums.slice(mid));
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) res.push(left[i] <= right[j] ? left[i++] : right[j++]);
  return res.concat(left.slice(i), right.slice(j));
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sorting Algorithms.