· By John Kavanagh

Sort an Array in TypeScript: Merge Sort and Its Space Cost

Red, yellow, green, and blue pencils lie in an ordered row on a white surface.
Image by William Warby, licensed from Unsplash.

Calling sort is the right answer surprisingly often. It is also an excellent way to avoid learning how sorting works, which is why LeetCode's Sort an Array exercise rules out the built‑in sort and asks for O(n log n) time with as little extra space as possible.

I like merge sort as the first implementation to reason about. Its decision is local: given two already sorted runs, take the smaller next value. The complication is storage. This version uses a linear buffer, so it does not achieve the smallest auxiliary‑space bound available. I'll show an iterative heapsort alternative as well, rather than quietly ignoring that part of the prompt.

Both implementations below sort the supplied array in place from the caller's perspective and return that same array. Only heapsort uses constant auxiliary space. Those are different promises, and the phrase "in place" can conceal the difference unless we spell it out.


Split Ranges, Not Arrays

The merge‑sort helper works on [start, end): start is included and end is excluded. A range shorter than two elements is already sorted. Every larger range splits at its midpoint, recursively sorts both halves, then merges them.

I pass indices instead of slicing. This avoids allocating new arrays for every recursive call and keeps the relationship with the original input visible. There is still one buffer, allocated at the beginning, with enough room for the whole array.

During a merge, left points into the first sorted half and right points into the second. write points into the buffer. Before each write, the buffer portion already produced is sorted and contains exactly the values consumed from the two halves. The next smallest unconsumed value must be at one of the two read positions.

If the right half is exhausted, take from the left. Otherwise, take from the left when it still has a value no larger than the right value. Everything else comes from the right. Checking exhaustion before comparing prevents a missing array element from entering the decision.

const sortArray = (nums: number[]): number[] => {
  const buffer = new Array<number>(nums.length);
  const merge = (start: number, end: number): void => {
    if (end - start < 2) return;
    const middle = start + Math.floor((end - start) / 2);
    merge(start, middle);
    merge(middle, end);
    let left = start;
    let right = middle;
    for (let write = start; write < end; write++) {
      if (right === end || (left < middle && nums[left] <= nums[right])) {
        buffer[write] = nums[left++];
      } else {
        buffer[write] = nums[right++];
      }
    }
    for (let index = start; index < end; index++) nums[index] = buffer[index];
  };
  merge(0, nums.length);
  return nums;
};

The merge writes into a separate buffer because overwriting nums immediately could destroy a value that the other read pointer hasn't consumed. After the merged range is complete, copying it back is safe. Reusing the same buffer across recursion works because each merge finishes before its caller starts merging the larger range.


Walk through the Merge That Does the Work

For [4, 1, 3, 1], recursion first produces sorted halves [1, 4] and [1, 3]. The final merge compares the two leading ones. It takes the left one, then the right one, then three, then the remaining four.

Choosing the left value on equality makes this merge stable: equal elements retain their original relative order. Plain numbers don't reveal that distinction, but records sorted by one field would. If the ones carried labels, the one originally in the left half would remain before the one originally in the right half.

The same logic handles negative numbers and repeated values without special branches. An already sorted input still passes through the merges; this version doesn't include an early check that the two halves already meet in order. Such a check can save copying on some inputs, but I prefer to establish the basic implementation before adding data‑dependent shortcuts.

An empty array is also harmless, although the exercise supplies at least one number. The initial range is empty and returns immediately. That extension makes the function convenient to test without changing the behaviour required by the problem.


The Cost Includes the Copying

Each recursion level merges disjoint ranges covering the array, so the comparisons and copies at that level take O(n) time. There are O(log n) levels. The worst‑case runtime is therefore O(n log n), including the copy‑back loop rather than pretending it is free.

The buffer uses O(n) auxiliary space. The recursive calls add O(log n) stack depth, because each call halves its range. The total extra space remains O(n). This is balanced recursion, quite different from traversing an input‑shaped chain whose depth could be n.

If the requirement is specifically constant auxiliary space, this merge sort is the wrong final choice. It remains useful when stable ordering and straightforward sequential merging matter, but its clarity does not cancel its allocation. An algorithm comparison ought to include the inconvenient column.


Heapsort When the Buffer is the Problem

A max heap stores a parent at least as large as its children. In an array, the children of index p are 2 * p + 1 and 2 * p + 2. After building the heap, its first value is the largest remaining number.

Swap that number to the end, shrink the active heap, and repair the root by moving it down until the parent rule holds again. The sorted suffix grows from right to left. The end argument below is excluded, so values already placed in the suffix are never pulled back into the heap.

const heapSort = (nums: number[]): number[] => {
  const siftDown = (start: number, end: number): void => {
    let parent = start;
    while (parent * 2 + 1 < end) {
      let child = parent * 2 + 1;
      if (child + 1 < end && nums[child + 1] > nums[child]) child++;
      if (nums[parent] >= nums[child]) return;
      [nums[parent], nums[child]] = [nums[child], nums[parent]];
      parent = child;
    }
  };
  for (let parent = Math.floor(nums.length / 2) - 1; parent >= 0; parent--) {
    siftDown(parent, nums.length);
  }
  for (let end = nums.length - 1; end > 0; end--) {
    [nums[0], nums[end]] = [nums[end], nums[0]];
    siftDown(0, end);
  }
  return nums;
};

Building the heap starts with the final possible parent and works backwards. Leaves already satisfy the heap rule. Each parent is repaired after its child subtrees have been repaired, making a whole‑array heap without inserting values one by one.

During extraction, choosing the larger child is essential. Swapping with the smaller child could leave the larger child above its parent in priority terms. Once the parent is at least as large as the larger child, it is large enough for both, and sifting can stop.

The iterative implementation uses O(1) auxiliary space. Heap construction takes O(n) time when the different subtree heights are counted, and the extractions take O(n log n) overall. Unlike merge sort, heapsort is not stable: a long‑distance swap can reverse equal records. Nothing in this integer‑only exercise requires stability.


Compare Results Without Copying the Implementation

For verification, I use a numeric built‑in sort on a copy as an independent reference. That doesn't violate the exercise: the implementation still performs its own sorting. Small exhaustive arrays containing negative values, zero, and duplicates catch far more edge cases than one large ascending array.

Useful additional checks are that both functions return the original array object, preserve the number of elements, and match the reference exactly. A sorted output alone is insufficient: accidentally dropping a duplicate can still leave a perfectly ordered result. Reverse order, all‑equal input, and odd lengths exercise different merge and heap paths.

My Kth Largest in a Stream article uses a heap when maintaining a small priority summary is enough. Here we need the complete order, and my binary search article shows one operation that can use that order afterwards. I would choose between these sorting implementations by the required stability and memory budget, then measure if runtime differences matter. The shortest code block is not a memory policy.


Planning a platform change?

I help teams make difficult platform work clearer, from architecture decisions and migrations to launch recovery, performance, and search visibility.