Merge Sort - Divide & Merge

• 1948 Jonathan wrote first program for merge.
• 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 arrays of 0 or 1 elements, then building up a newly sorted array
• Much more optimized sorting technique.

[3, 1, 2, 4, 1, 5, 2, 6, 4]

Pseudocode

[3, 2, 4, 1, 3]
 /           \ 
low          high
		/       \
[3,2,1]    [1,3]

mergeSort(arr,low,high){
if(low  >= high) return;
	mid = (low + high)/2
	mergeSort(arr,low,mid);
	mergeSort(arr,mid+1,high);
	merge(arr,low,mid,high)
	
}

Dry Run

[3, 2, 4, 1, 3]
 /           \ 
low          high
		/       \
[3,2,1]    [1,3]
 0 1 2      3 4

merge

code

function merge(arr, low, mid, high) {
    let temp = [];
    let left = low;
    let right = mid + 1;

    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp.push(arr[left]);
            left++;
        } else {
            temp.push(arr[right]);
            right++;
        }
    }

    while (left <= mid) {
        temp.push(arr[left]);
        left++;
    }

    while (right <= high) {
        temp.push(arr[right]);
        right++;
    }

    for (let i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

function mS(arr, low, high) {
    if (low >= high) return;
    let mid = Math.floor((low + high) / 2);
    mS(arr, low, mid);
    mS(arr, mid + 1, high);
    merge(arr, low, mid, high);
}

function mergeSort(arr) {
    mS(arr, 0, arr.length - 1);
    return arr;
}

console.log(mergeSort([1, 24, 1, 15, 123, 521, 12]));

Time Complexity - O(nlog⁡n)

Space Complexity - O(n)

Another Explanation

Merging 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.
• The function should run in O(n + m) time and O(n + m) space and should not modify the parameters passed to it.

Merging 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 out results and move on to the next value in the first array.
  • If 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 movie on to the next value in the second array.
  • Once we exhaust one array, push in all remaining values from the 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;

}

mergeSort Pseudocode

• Break up the array into halves until you have arrays that are empty or have one element.
• 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;
	let mid = Math.floor(arr.length/2);
	let left = mergeSort(arr.slice(0,mid));
	let right = mergeSort(arr.slice(mid));
	return merge(left , right);
}

Time Complexity

Sorting Exercise - merge helper

Given two sorted arrays, write a function called merge which accepts two SORTED arrays and returns a new array with both of the values from each array sorted.

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

As before, the function should default to sorting numbers in ascending order. If you pass in a comparator function as a third argument, this comparator is what will be used. (Note that the input arrays will always be sorted according to the comparator!)

Also, do not use the built in .sort method! We're going to use this helper to implement a sort, so the helper itself shouldn't depend on a sort.

Examples

1. var arr1 = [1,3,4,5]; 2. var arr2 = [2,4,6,8]; 3. merge(arr1,arr2) // [1,2,3,4,4,5,6,8] 4.   5. arr1 // [1,3,4,5]; 6. arr2 // [2,4,6,8]; 7.   8. var arr3 = [-2,-1,0,4,5,6]; 9. var arr4 = [-3,-2,-1,2,3,5,7,8]; 10.   11. merge(arr3,arr4); // [-3,-2,-2,-1,-1,0,2,3,4,5,5,6,7,8] 12.   13. var arr5 = [3,4,5] 14. var arr6 = [1,2] 15.   16. merge(arr5,arr6) // [1,2,3,4,5] 17.   18. var names = ["Bob", "Ethel", "Christine"] 19. var otherNames = ["M", "Colt", "Allison", "SuperLongNameOMG"] 20.   21. function stringLengthComparator(str1, str2) { 22. return str1.length - str2.length; 23. } 24.   25. merge(names, otherNames, stringLengthComparator); // ["M", "Bob", "Colt", "Ethel", "Allison", "Christine", "SuperLongNameOMG"]

function merge(arr1,arr2,comparator){
    let results = [];
    let i = 0;
    let j = 0;
   const compare = comparator || function(a, b) {
    return a - b;
  };
    while(i < arr1.length && j < arr2.length){
        if(compare(arr1[i], arr2[j]) <= 0){
            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 Sort

Implement the merge sort algorithm. Given an array, this algorithm will sort the values in the array. The functions take 2 parameters: an array and an optional comparator function.

The comparator function is a callback that will take two values from the array to be compared. The function returns a negative value if the first value is less than the second, a positive value if the first value is greater than the second, and 0 if both values are equal.

The default comparator you provide should assume that the two parameters are numbers and that we are sorting the values from smallest to largest.

Here's some guidance for how merge sort should work:

• Break up the array into halves until you can compare one value with another
• Once you have smaller sorted arrays, merge those arrays with other sorted pairs 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

In order to implement this function, you'll also need to implement a merge function that takes in two sorted arrays and a comparator and returns a new sorted array. You implemented this function in the previous exercise, so copy and paste that code here.

You can read more merge sort here: https://www.rithmschool.com/courses/javascript-computer-science-fundamentals/intermediate-sorting-algorithms

Examples

1. mergeSort([4, 20, 12, 10, 7, 9]); // [4, 7, 9, 10, 12, 20] 2. mergeSort([0, -10, 7, 4]); // [-10, 0, 4, 7] 3. mergeSort([1, 2, 3]); // [1, 2, 3] 4. mergeSort([]); 5.   6. var nums = [4, 3, 5, 3, 43, 232, 4, 34, 232, 32, 4, 35, 34, 23, 2, 453, 546, 75, 67, 4342, 32]; 7. mergeSort(nums); // [2, 3, 3, 4, 4, 4, 5, 23, 32, 32, 34, 34, 35, 43, 67, 75, 232, 232, 453, 546, 4342] 8.   9. var kitties = ["LilBub", "Garfield", "Heathcliff", "Blue", "Grumpy"]; 10.   11. function strComp(a, b) { 12. if (a < b) { return -1;} 13. else if (a > b) { return 1;} 14. return 0; 15. } 16.   17. mergeSort(kitties, strComp); // ["Blue", "Garfield", "Grumpy", "Heathcliff", "LilBub"] 18.   19. var moarKittyData = [{ 20. name: "LilBub", 21. age: 7 22. }, { 23. name: "Garfield", 24. age: 40 25. }, { 26. name: "Heathcliff", 27. age: 45 28. }, { 29. name: "Blue", 30. age: 1 31. }, { 32. name: "Grumpy", 33. age: 6 34. }]; 35.   36. function oldestToYoungest(a, b) { 37. return b.age - a.age; 38. } 39.   40. mergeSort(moarKittyData, oldestToYoungest); // sorted by age in descending order

function merge(arr1, arr2, comparator) {
  let result = [];
  let i = 0;
  let j = 0;
  let compare = comparator || function(a, b) {
    return a - b;
  };

  while (i < arr1.length && j < arr2.length) {
    if (compare(arr1[i], arr2[j]) <= 0) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  return result;
}

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