hard

Minimum Adjacent Swaps to Sort an Array

Find the minimum number of adjacent swaps needed to sort an array of distinct integers.

1. Define the problem

Minimum Adjacent Swaps to Sort an Array

Given an array nums of distinct integers, return the minimum number of adjacent swaps needed to sort it in ascending order. Bubble sort only ever swaps adjacent out-of-order pairs, and each such swap fixes exactly one inversion — so the number of swaps bubble sort performs is already the minimum possible. Simulating it directly is O(n^2), which is too slow here; instead, count inversions in O(n log n) using a merge-sort-style count, which gives the same answer bubble sort would arrive at, without the wasted comparisons.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -109 ≤ numsi ≤ 109
  • All values in nums are distinct

Example

Inputnums = [4, 3, 1, 2]
Output5

Explanation There are 5 inversions in [4, 3, 1, 2]: (4,3), (4,1), (4,2), (3,1), (3,2) — each needs exactly one adjacent swap to fix.

2. Know the words first

In plain terms

Inversion
A pair of positions (i, j) with i before j where numsi is bigger than numsj — exactly the kind of pair bubble sort fixes with one swap.
3. Visualize the solution

Count inversions with a merge-sort sweep

Count inversions with a merge-sort sweep
Statussplit

Split [4, 3, 1, 2] into [4, 3] and [1, 2], and recurse on each half.

What happens in this step

[4, 3, 1, 2] → left [4, 3], right [1, 2]

Splitting in half is what makes this O(n log n) instead of O(n^2) — each half's inversions get counted independently before the halves are merged back together.
Step 1 of 4

Steps to visualize

  1. The row is the whole array, four cells wide; the highlight shows the part being worked on.
  2. Split the array in half and recursively count inversions in each half.
  3. Merge the two sorted halves back together.
  4. Whenever an element from the right half is placed before remaining elements of the left half, every one of those remaining left elements forms an inversion with it — add that count.
  5. The sum of all these counts, across every merge step, is the minimum number of adjacent swaps to sort the array.
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.

Count inversions with a merge-sort sweep
Statussplit

Split [4, 3, 1, 2] into [4, 3] and [1, 2], and recurse on each half.

What happens in this step

[4, 3, 1, 2] → left [4, 3], right [1, 2]

Splitting in half is what makes this O(n log n) instead of O(n^2) — each half's inversions get counted independently before the halves are merged back together.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function minSwapsToSort(nums) {
  function mergeCount(arr, left, right) {
    if (right - left <= 1) {
      return 0;
    }

    const mid = Math.floor((left + right) / 2);
    let count = mergeCount(arr, left, mid) + mergeCount(arr, mid, right);

    const merged = [];
    let i = left;
    let j = mid;

    while (i < mid && j < right) {
      if (arr[i] <= arr[j]) {
        merged.push(arr[i]);
        i++;
      } else {
        merged.push(arr[j]);
        j++;
        count += mid - i;
      }
    }

    while (i < mid) merged.push(arr[i++]);
    while (j < right) merged.push(arr[j++]);

    for (let k = 0; k < merged.length; k++) {
      arr[left + k] = merged[k];
    }

    return count;
  }

  const copy = nums.slice();
  return mergeCount(copy, 0, copy.length);
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [4, 3, 1, 2]5example from the docstring
nums = [1, 2, 3, 4, 5]0already sorted, zero swaps needed
nums = [5, 4, 3, 2, 1]10worst case, maximum possible inversions
nums = [10]0smallest valid input, a single element
nums = [2, 1]1boundary case, exactly one inversion
nums = [1, 3, 2]1only one pair out of order
nums = [3, 1, 2, 5, 4]3a permutation with inversions spread across non-adjacent positions

Keep reading