Merge sort JavaScript algorithm

Merge sort is a popular sorting algorithm that follows the divide-and-conquer approach. This JavaScript algorithm recursively splits the input array into smaller halves, sorts them, and then merges them back together to produce the final sorted array.

Here’s the step-by-step breakdown of the merge sort algorithm:

1. Splitting the array: The algorithm starts by dividing the input array into two halves. This process continues recursively until the array contains only one element or is empty. This is the base case of the recursion.
2. Sorting the halves: Once the array is divided into smaller halves, the algorithm sorts them individually using the merge sort algorithm. This step is performed recursively until the base case is reached.
3. Merging the sorted halves: After sorting the smaller halves, the algorithm merges them back together to obtain the final sorted array. It compares the elements from both halves and adds the smaller element to the result array. This process continues until all the elements from both halves are merged.
4. Returning the result: Finally, the algorithm returns the sorted array obtained from the merging process.

Merge sort JavaScript example

Simple example code implementation of the merge sort algorithm in JavaScript:

function mergeSort(array) {
  if (array.length <= 1) {
    return array; // Base case: array is already sorted
  }

  // Split the array into two halves
  const middle = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, middle);
  const rightHalf = array.slice(middle);

  // Recursively sort the two halves
  const sortedLeft = mergeSort(leftHalf);
  const sortedRight = mergeSort(rightHalf);

  // Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Compare elements from the left and right arrays and add the smaller one to the result
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add any remaining elements from the left and right arrays
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }
  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

// Example usage:
const array = [5, 2, 9, 1, 7, 6];
const sortedArray = mergeSort(array);
console.log(sortedArray);

Output:

This algorithm has a time complexity of O(n log n) and provides a stable sorting solution. You can test the algorithm by providing your own array in the array variable and running the code.

Comment if you have any doubts or suggestions on this JS sorting algorithm topic.

Note: The All JS Examples codes are tested on the Firefox browser and the Chrome browser.

OS: Windows 10

Code: HTML 5 Version