Merge Sort

Faster Sorts

. There is a family of sorting algorithms that can improve time complexity from O(n^2) to O(n log n) . There's a tradeoff between efficiency and simplicity . The more efficient algorithms are much less simple, and generally take longer to understand

Merge Sort

. It's a combination of two things - merging and sorting! . Exploits the fact that arrays of 0 or 1 element are always sorted . Works by decomposing an array into smaller sorted array of 0 or 1 elements, then building up a newly sorted array

Mergin Arrays

. In order to implement merge sort, it's useful to first implement a function responsible for merging two sorted arrays

. Given two arrays which are sorted, this helper function should create a new array which is also sorted, and consists of all of the elements in the two input arrays

. This function should run O(n + m) time and O(n + m) space and should not modify the parameters passed to it.

Mergin Arrays Pseudocode

. Create an empty array, take a look at the smallest values in each input array

. While there are still values we haven't looked at...

. If the value in the first array is smaller than the value in the second array, push the value in the first array into our results and move on to the next value in the first array.

. Id the value in the first array is larger than the value in the second array, push the value in the second array into our results and move on to the next value in the second array

. Once we exhaust one array, push in all remaining values from the other array

Merging Arrays Implementation

function merge(arr1, arr2) {
  let results = [];
  let i = 0;
  let j = 0;
  while(i < arr1.length && j < arr2.length) {
    if (arr2[j] > arr1[i]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  while(i < arr1.length) {
    results.push(arr1[i])
  }

  while(j < arr2.length) {
    results.push(arr2[j])
  }

  return results;
}