medium

Sort an Array

Sort an array of integers in ascending order without using a built-in sort.

1. Define the problem

Sort an Array

Given an array of integers nums, sort the array in ascending order and return it, without using a built-in sort function. Implement quick sort : pick a pivot , partition the array around it so smaller values land on the left and larger values on the right, then recurse on each piece.

Constraints

  • 1 ≤ nums.length ≤ 5 × 104
  • -5 × 104 ≤ numsi ≤ 5 × 104

Example

Inputnums = [5, 2, 3, 1]
Output[1, 2, 3, 5]

Explanation Sorting the array in ascending order gives [1, 2, 3, 5].

2. Know the words first

In plain terms

Pivot
The value everything else in the current piece gets compared against for one partition step.
Partition
The single pass that rearranges a piece of the array so everything smaller than the pivot ends up left of it, larger ends up right.
3. Visualize the solution

Partition around a pivot, then recurse on each piece

Partition around a pivot, then recurse on each piece
Statusstart

Pick a pivot (last element, 5) and partition the whole array around it.

What happens in this step

array: [8, 3, 1, 7, 0, 5]
pivot = arr[5] = 5 (last element)

The partition walks j from lo to hi-1, swapping every value less than 5 toward the front; the pivot itself moves into its final position afterward.
Step 1 of 4

Steps to visualize

  1. Pick a pivot (commonly the last element) and partition the array around it in one pass.
  2. The pivot lands in its final sorted index; everything smaller sits to its left, everything larger to its right.
  3. Recursively repeat the same partition step on the left piece.
  4. Recursively repeat the same partition step on the right piece.
  5. Once every piece is down to zero or one elements, the array is fully sorted.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Partition around a pivot, then recurse on each piece
Statusstart

Pick a pivot (last element, 5) and partition the whole array around it.

What happens in this step

array: [8, 3, 1, 7, 0, 5]
pivot = arr[5] = 5 (last element)

The partition walks j from lo to hi-1, swapping every value less than 5 toward the front; the pivot itself moves into its final position afterward.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function sortArray(nums) {
  function partition(arr, lo, hi) {
    const randomIndex = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[randomIndex], arr[hi]] = [arr[hi], arr[randomIndex]];

    const pivot = arr[hi];
    let i = lo;

    for (let j = lo; j < hi; j++) {
      if (arr[j] < pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }

    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  function quickSort(arr, lo, hi) {
    if (lo >= hi) return;
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }

  quickSort(nums, 0, nums.length - 1);
  return nums;
}
Time
O(n log n) average, O(n²) worst case
Space
O(log n) average for the recursion stack
6. Test cases

Test cases

InputExpectedCovers
nums = [5, 2, 3, 1][1, 2, 3, 5]example from the docstring
nums = [1, 2, 3, 4, 5][1, 2, 3, 4, 5]already sorted input, the classic worst-case trigger for a fixed pivot
nums = [5, 4, 3, 2, 1][1, 2, 3, 4, 5]reverse sorted input
nums = [4, 2, 4, 1, 2][1, 2, 2, 4, 4]duplicate values
nums = [-3, 0, -1, 2, -5][-5, -3, -1, 0, 2]negative values mixed with positive values
nums = [7][7]smallest valid input, a single element
nums = [][]empty array, nothing to sort
nums = [3, 3, 3][3, 3, 3]every value identical

Keep reading