Merge Sort Algorithm - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki
Merge Sort
What is it?
The merge sort method is frequently referred to as a "Divide and Conquer" method. In taking an array that is all jumbled, things become easier to sort into proper order if you divide the array into two sections - left side and right side. Then, once you sort these two separate arrays, it becomes easier to merge them together and sort as you go.
Visual
Pseudo Code
ALGORITHM Mergesort(arr)
DECLARE n <-- arr.length
if n > 1
DECLARE mid <-- n/2
DECLARE left <-- arr[0...mid]
DECLARE right <-- arr[mid...n]
// sort the left side
Mergesort(left)
// sort the right side
Mergesort(right)
// merge the sorted left and right sides together
Merge(left, right, arr)
ALGORITHM Merge(left, right, arr)
DECLARE i <-- 0
DECLARE j <-- 0
DECLARE k <-- 0
while i < left.length && j < right.length
if left[i] <= right[j]
arr[k] <-- left[i]
i <-- i + 1
else
arr[k] <-- right[j]
j <-- j + 1
k <-- k + 1
if i = left.length
set remaining entries in arr to remaining values in right
else
set remaining entries in arr to remaining values in left
Algorithm
It starts with defining our function, which we'll call mergeSort, and it will take in the array that we want to perform the merge sort on. To begin this, we want what will be called a "pivot" which will define the split between how we'll divide the array. We will set the variable of "mid" as the middle point of the array, and this will be our pivot.
Then we actually need to divide our array. We'll make a leftArray variable to include the array at from index position 0, to our mid variable. Then we'll make rightArray go from our mid variable to the end of our array. Now we've partitioned our array.
Now we'll need to create a function inside of our function that accepts our two partitioned sections of our original array. Inside this function we'll instantiate a variable called mergedArray that will be an empty array, which we'll pass our final result into.
Now we'll set the beginning number of both of our partitioned arrays to 0. Next we'll go into our loop.
We'll instantiate a while loop that runs as long as the index position of our left array is less than the length of our left array. AND we'll have the same condition on our right array too.
As long as both of those conditions are true, we'll do the following work:
If the value of the current index position of leftArray is less than the value of the current index position of the rightArray, push the value of the current index position of leftArray into our previously empty mergedArray array, and then increase the index position by 1, then continue. If the same is true but for the right array, do the same thing.
Now we need to combine our left and right arrays. We'll do that via concatenation. Now all we have to do, is call and return our merge function, calling the mergeSort function inside of it, accepting the leftArray, and call mergeSort again, accepting the rightArray. The merge function will then take these two array, called by the mergeSort(s) inside, and will arrange them as needed. You now have a completely sorted array through a merge sorting method.
function mergeSort(arr) {
// if the array is 1 number return array
if (arr.length < 2) return arr;
// set the mid point to the length of the array div by 2, rounded down
const mid = Math.floor(arr.length / 2);
// create left/right slice of array from first index through mid
const leftArray = arr.slice(0, mid);
const rightArray = arr.slice(mid);
// function called merge that accepts slices
const merge = (leftArray, rightArray) => {
// initialize an empty array to hold the result
const mergedArray = [];
// set leftIndex and rightIndex to a 0 to track indexes as we sort
let leftIndex = 0;
let rightIndex = 0;
// while leftIndex & rightIndex are shorter than the length of their arrays
// push the smaller value and increment index of that array
while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
// if leftArray item < rightArray item
if (leftArray[leftIndex] < rightArray[rightIndex]) {
// push item to mergedArray and increment
mergedArray.push(leftArray[leftIndex]);
leftIndex++;
continue;
}
// right is smaller
mergedArray.push(rightArray[rightIndex]);
rightIndex++;
}
// concatenate sorted array slices and return the result
return mergedArray.concat(leftArray.slice(leftIndex)).concat(rightArray.slice(rightIndex));
}
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
mergeSort([24, 103, 7, 542, 198, 747, 525, 885, 9, 17, 22, 14, 2, 9, 7]);