Merge Sort

Mark as Completed

Lesson

Write a function to sort an input array using the merge sort algorithm. Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts each half using recursion, and then merges the two sorted halves to output one sorted array in ascending order. Your function should take in an array as input and return a sorted array.

Walkthrough

The merge sort algorithm is a recursive algorithm that works by dividing the input array into two halves, sorting each half, and then merging the two sorted halves. We'll start by writing a function to merge two sorted arrays, as we'll need this helper function to implement the merge sort algorithm.

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

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

The merge
function takes in two arrays, left
and right
, and returns a new sorted array that merges the two input arrays. We start by initializing an empty array result
, and two indices, leftIndex
and rightIndex
, to keep track of the current positions in the left and right arrays. We loop through the left and right arrays until we've gone through all the elements in either array. In each iteration, we compare the current element in the left array with the current element in the right array. If the element in the left array is smaller, we add it to the result array and increment leftIndex
. Otherwise, we add the element in the right array to the result array and increment rightIndex
. Finally, we concatenate any remaining elements in either the left or right array to the result array and return the sorted array.Next, we can write the mergeSort
function to implement the merge sort algorithm. The mergeSort
function takes in an array and recursively sorts it using the merge
function.

function mergeSort(array) {
  const length = array.length;

  if (length < 2) {
    return array;
  }

  const middle = Math.floor(length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

The mergeSort
function starts by checking if the length of the input array is less than 2. If so, the array is already sorted and we can return it. Otherwise, we find the middle index of the array using Math.floor(length / 2)
, and use the slice
method to create new left and right arrays. We then recursively call mergeSort
on the left and right arrays, which will continue to divide the arrays into smaller halves until they are sorted. Finally, we return the merged and sorted left and right arrays using the merge
function.

Big O Complexity Analysis:

The merge sort algorithm has a time complexity of O(n log n), where n is the number of elements in the input array. The algorithm works by recursively dividing the input array in half, sorting each half, and then merging the sorted halves.

In each level of recursion, the array is divided into two halves, and the merge
function is called once to merge the two halves. The merge
function takes O(n) time to merge two arrays of length n/2, and since there are log n levels of recursion (because we're dividing the array in half each time), the total time complexity of the merge
function is O(n log n).The mergeSort
function also takes O(n log n) time to sort the input array, since it recursively divides the array in half and then calls the merge
function at each level of recursion.

The space complexity of the merge sort algorithm is O(n), since the algorithm creates a new temporary array to merge the left and right halves at each level of recursion. This temporary array has a length of n, which is the maximum size of the input array. Therefore, the space complexity of the merge sort algorithm is proportional to the size of the input array.

Previous Lesson Next Lesson