AlgoMaster Logo

Sort an Array

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

The problem looks trivial until you read the constraint: built-in sort functions are banned. The task is to implement a sorting algorithm from scratch that runs in O(n log n) time.

With n up to 50,000, an O(n^2) algorithm like bubble sort or selection sort is too slow. The viable options are the O(n log n) comparison sorts: merge sort, heap sort, or quicksort with randomized pivot selection.

The choice between them comes down to trade-offs. Merge sort is guaranteed O(n log n) but uses O(n) extra space. Quicksort is faster in practice and uses less space, but degrades to O(n^2) unless the pivot is randomized.

Key Constraints:

  • 1 <= nums.length <= 5 * 10^4 → With n up to 50,000, an O(n^2) sort performs on the order of n^2 / 2 = 1.25 billion comparisons. That rules out selection sort and bubble sort as the primary solution. We need O(n log n).
  • -5 * 10^4 <= nums[i] <= 5 * 10^4 → Every value fits in a 32-bit integer, so no overflow concerns. The value range spans 100,001 possible values, which makes counting sort viable as a special case, but the focus here is a general-purpose comparison sort.

Approach 1: Selection Sort (Brute Force)

Intuition

Find the smallest element and put it first, find the next smallest and put it second, and so on. For each position in the array, scan the remaining unsorted portion to find the minimum and swap it into place.

This is easy to implement but does redundant work. Each search for the minimum re-scans elements that earlier searches already compared, and there is no way to reuse that work within this framework. That is why it stays at O(n^2).

Algorithm

  1. For each index i from 0 to n - 2, find the index of the minimum element in the subarray from i to n - 1.
  2. Swap the element at index i with the element at the minimum index.
  3. After processing all positions, the array is sorted.

Example Walkthrough

Input:

0
5
1
2
2
3
3
1
nums

After scanning, minimum is 1 at index 3. Swap with index 0:

0
1
1
2
2
3
3
5

Code

Each position triggers a full linear scan that discards every comparison made before it. The next approach removes this waste by splitting the array into smaller subproblems and combining the sorted results in linear time.

Approach 2: Merge Sort

Intuition

Merge sort is the divide-and-conquer sorting algorithm. Two sorted halves can be merged into one sorted array in O(n) time by comparing the front elements of each half and taking the smaller one. That merge operation is the whole basis of the algorithm.

The strategy: split the array in half, recursively sort each half, then merge the two sorted halves. The recursion bottoms out at single elements, which are already sorted. All the comparison work happens during the merge step, and each level of recursion does O(n) total merge work across all the subarrays at that level. With O(log n) levels, the total time is O(n log n).

The cost is space. Each merge step needs a temporary array to hold the merged result, which adds O(n) extra space. In return, merge sort is O(n log n) in all cases, with no input that degrades it to O(n^2).

Algorithm

  1. If the array has 0 or 1 elements, it's already sorted. Return it.
  2. Find the middle index: mid = left + (right - left) / 2.
  3. Recursively sort the left half (from left to mid).
  4. Recursively sort the right half (from mid + 1 to right).
  5. Merge the two sorted halves into a single sorted array using a two-pointer technique.

Visualization and Code

Loading animation...

Merge sort guarantees O(n log n) but uses O(n) extra space. The next approach sorts in place, reducing the extra space to the O(log n) recursion stack while keeping O(n log n) expected time.

Approach 3: Randomized Quick Sort

Intuition

Quicksort inverts merge sort. Instead of splitting evenly and doing the comparison work during the merge, quicksort does the comparison work during the split. It picks a pivot element, partitions the array so that everything less than or equal to the pivot goes left and everything greater goes right, then recursively sorts the two sides. After partitioning, the pivot is already in its final sorted position, so there is no merge step.

Pivot selection is the hazard. Always picking the first or last element as the pivot causes O(n^2) behavior on sorted or nearly-sorted input, because one partition holds n - 1 elements and the other holds 0, repeating n times. Picking the pivot at random fixes this. With a random pivot, the expected number of comparisons is O(n log n), and the chance of repeatedly picking near-extreme pivots drops off exponentially with n.

This LeetCode problem includes sorted and adversarial test cases that force O(n^2) behavior out of a fixed-pivot quicksort, which is why the random pivot is required to pass.

Algorithm

  1. If the subarray has 0 or 1 elements, return (base case).
  2. Pick a random index in the range [left, right] and swap it with right (move the pivot to the end).
  3. Partition the array: maintain a pointer storeIdx at left. Scan from left to right - 1. Whenever an element is less than or equal to the pivot, swap it with the element at storeIdx and increment storeIdx.
  4. Swap the pivot (at right) with the element at storeIdx. Now the pivot is at its correct position.
  5. Recursively sort the left partition (left to storeIdx - 1) and the right partition (storeIdx + 1 to right).

Example Walkthrough

1Initial array. Random pivot index=2, pivot value=3. Swap pivot to end.
0
storeIdx
5
i
1
2
2
1
3
3
pivot=3
1/6

Code