[Intermediate Sorting Algotithms] Merge sort

Intermediate sort

• merge sort
• quick sort
• radix sort

 

time complexity from O(n^2) to O(n log n)

 

Merge sort

• spliting up + merging + sorting
• exploits the fact that arrays of 0 or 1 element are always sorted
• works by decomposing an array into smaller arrays of 0 or 1 elements, then building up a newly sorted array

 

How does it work?

 

1. Merging arrays: merge 2 sorted 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 in O(n+m) time and O(n+m) space and should not modify the parameters passed to it.

 

Pseudocode

• 1. Create an empty array, take a look at the smallest values in each input array
  • while loop, starting i and j at 0
• 2. While there are still values we haven't looked at
  • If the value in the first 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
  • If the value in the first 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 other array

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]);
    i++;
  }
  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  return results;
}

merge([1, 10, 50], [2, 14, 99, 100]);

 

2. Merge sort Pseudocode

• Break up the array into halves until you have arrays that are empty or have one element
  • .slice (0 - middle)
  • using recursively (base case: array's length is less or equal to 1)
• Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the full length of the array
• Once the array has been merged back together, return the merged(and sorted) array.

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

mergeSort([10, 24, 76, 73]);

 

 

Big O

Time complexity (Best)	Time complexity (Average)	Time complexity (Worst)	Space complexity
O(n log n)	O(n log n)	O(n log n)	O(n)

O(log n) decomposition + O(n) comparisons per decomposition