DSA problem
Sort an Array
Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(n log n) time complexity and with the smallest space complexity possible.
This task is the classic litmus test for any comparison-based sorting algorithm. The naive choices — bubble sort, insertion sort, selection sort — all run in O(n²) time, which immediately fails the constraint at the upper end of n. The interview-grade options that hit O(n log n) are merge sort, heap sort, and quicksort (in expectation). Of these, merge sort is the most predictable and is also stable, meaning equal elements keep their original relative order.
The merge sort idea is divide-and-conquer. Recursively split the array into halves until each piece has size one (which is trivially sorted), then repeatedly merge two sorted halves into one larger sorted run. The merge step itself is linear: walk two pointers through the two halves and copy the smaller front element each time. The recursion depth is O(log n), and each level merges a total of n elements, giving O(n log n) overall.
The canonical implementation operates in place on the input array using a scratch buffer of size n for the merge step. We expose a thin sortArray entry point that calls mergeSort(arr, lo, hi) with inclusive bounds; mergeSort halves the range, recurses on each side, then calls merge(arr, lo, mid, hi) which copies the two sorted sub-ranges into a temporary buffer and writes them back in sorted order. The result is O(n log n) time, O(n) extra space, and a stable sort.
Examples
nums = [5,2,3,1][1,2,3,5]nums = [5,1,1,2,0,0][0,0,1,1,2,5]nums = [-4,0,7,4,9,-5,-1,0,-7,-1][-7,-5,-4,-1,-1,0,0,4,7,9]Constraints
- 1 <= nums.length <= 5 * 10^4
- -5 * 10^4 <= nums[i] <= 5 * 10^4
- The required time complexity is O(n log n).
- You must not use built-in sort routines.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.