Sort List (Merge Sort on Linked List)

Sort a singly linked list in O(N log N) time using O(1) auxiliary space.

Merge two sorted integer arrays nums1 and nums2 into nums1 as one sorted array.

Count of Smaller Numbers After Self

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Searching & Sorting AlgorithmsIntermediate LevelStudy Time: 25 mins

Merge Sort Algorithm

Merge Sort is a stable Divide and Conquer algorithm that recursively splits an array into halves until single elements remain, then merges sorted halves back together.

Merge Sort Visualizer

Array loaded. Trigger Merge Sort to visualize recursive divide & conquer tree decomposition.

FULL INPUT ARRAY CONTAINER

45

[0]

10

[1]

55

[2]

30

[3]

20

[4]

40

[5]

Left Subset [0..Mid]Inactive

Waiting for split...

Right Subset [Mid+1..N]Inactive

Waiting for split...

Speed:

Real-world analogy: Merging Sorted Decks

Divide

Merge

Hover over items for details

Divide cards into two piles. Sort each pile, then merge them back by comparing the top card of each pile and picking the smaller one.

Divide= Splits array into two equal halves.
Merge= Combines two sorted sub-arrays into one ordered array.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapMerge Sort: O(N log N) Linearithmic Time

Hover curves to inspect classes

Time Steps (N=500)

~4,483 steps (Linearithmic)

O(N log N) Linearithmic Time

Space Footprint

O(N) Aux Memory

Memory growth rate as N expands.

Performance Rank

Moderate Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
Best / Average / Worst Case	O(N log N)	O(N)

Code implementations

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}