JavaScript Program for Merge Sort Algorithm

A JavaScript program for merge sort uses a mergeSort function that splits the array into halves recursively and merges sorted halves with a merge helper function, like function mergeSort(arr) { if (arr.length < 2) 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); }.

Examples

Input[3, 1, 4, 2]

Output[1, 2, 3, 4]

Input[10, 5, 2, 8, 7, 6]

Output[2, 5, 6, 7, 8, 10]

Input[]

Output[]

How to Think About It

To sort an array using merge sort, first split the array into two halves until each part has one or zero elements. Then, merge these small parts back together in order by comparing their elements one by one. This way, you build up a fully sorted array from smaller sorted pieces.

Algorithm

1

Check if the array length is less than 2; if yes, return the array as it is already sorted.

2

Find the middle index of the array.

3

Split the array into left and right halves using the middle index.

4

Recursively apply merge sort on the left half.

5

Recursively apply merge sort on the right half.

6

Merge the two sorted halves into one sorted array and return it.

Code

javascript

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
  if (arr.length < 2) 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);
}

const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array));

Output

[3, 9, 10, 27, 38, 43, 82]

Dry Run

Let's trace the array [38, 27, 43, 3] through the merge sort code

1

Split array

Split [38, 27, 43, 3] into [38, 27] and [43, 3]

2

Split left half

Split [38, 27] into [38] and [27]

3

Split right half

Split [43, 3] into [43] and [3]

4

Merge left halves

Merge [38] and [27] into [27, 38]

5

Merge right halves

Merge [43] and [3] into [3, 43]

6

Merge final halves

Merge [27, 38] and [3, 43] into [3, 27, 38, 43]

Step	Left Array	Right Array	Merged Result
1	[38, 27]	[43, 3]
2	[38]	[27]	[27, 38]
3	[43]	[3]	[3, 43]
4	[27, 38]	[3, 43]	[3, 27, 38, 43]

Why This Works

Step 1: Divide the array

The code splits the array into smaller parts until each part has one or zero elements using slice and recursion.

Step 2: Merge sorted parts

The merge function compares elements from two sorted arrays and builds a new sorted array by picking the smaller element each time.

Step 3: Build sorted array

By merging sorted halves repeatedly, the code combines all parts into one fully sorted array.

Alternative Approaches

Iterative Merge Sort

javascript

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSortIterative(arr) {
  let step = 1;
  while (step < arr.length) {
    let left = 0;
    while (left + step < arr.length) {
      const mid = left + step;
      const right = Math.min(left + 2 * step, arr.length);
      const merged = merge(arr.slice(left, mid), arr.slice(mid, right));
      for (let i = 0; i < merged.length; i++) {
        arr[left + i] = merged[i];
      }
      left += 2 * step;
    }
    step *= 2;
  }
  return arr;
}

console.log(mergeSortIterative([38, 27, 43, 3, 9, 82, 10]));

This approach avoids recursion by merging subarrays iteratively, which can be easier to understand for some but is more complex to code.

Using JavaScript's built-in sort

javascript

const arr = [38, 27, 43, 3, 9, 82, 10];
const sorted = arr.sort((a, b) => a - b);
console.log(sorted);

This is the simplest way to sort in JavaScript but does not teach the merge sort algorithm.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort splits the array into halves recursively (log n splits) and merges all elements (n per merge), resulting in O(n log n) time.

Space Complexity

It requires extra space to hold temporary arrays during merging, so space complexity is O(n).

Which Approach is Fastest?

Built-in sort is fastest for practical use, but merge sort guarantees O(n log n) time and is stable. Iterative merge sort avoids recursion but is more complex.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Learning algorithm and stable sorting
Iterative Merge Sort	O(n log n)	O(n)	Avoiding recursion, large data
Built-in sort	Varies (usually O(n log n))	O(1) or O(n)	Quick sorting in real projects