Created
February 7, 2021 13:21
-
-
Save ivarprudnikov/0617c3ba4e2cf6abaaad0dd48f2cf459 to your computer and use it in GitHub Desktop.
Merge sort in javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var arr = [0,5,7,3,4,9,6,2,1,8]; | |
var ans = [0,1,2,3,4,5,6,7,8,9]; | |
// Split array into smaller chunks recursively [a,b,c,d] => [a,b] and [c,d] | |
// At the bottom (or top of stack) start merging those back | |
// O(NlogN) | |
function mergeSort(a, startIdx, endIdx) { | |
if (startIdx < endIdx) { | |
var mid = Math.floor((startIdx + endIdx)/2); | |
mergeSort(a, startIdx, mid); | |
mergeSort(a, mid + 1, endIdx); | |
merge(a, startIdx, mid, endIdx); | |
} | |
} | |
// sort elements in between given indexes and replace those in the original array | |
// eg: [6,5,4,1], 0, 1, 2 => [4,5,6,1] | |
function merge(arr, startIdx, midIdx, endIdx) { | |
var tmpArr = []; // collect sorted result here | |
var tmpLeftStart = startIdx; // left side pointer | |
var tmpRightStart = midIdx + 1; // right side pointer | |
var tmpCurrentIdx = 0; // track the amount of insertions | |
for(var i = startIdx; i <= endIdx; i++) { | |
if (tmpLeftStart > midIdx) { // left side reached the end | |
tmpArr[tmpCurrentIdx++] = arr[tmpRightStart++]; // first element in the right side should be used | |
} else if (tmpRightStart > endIdx) { // right side reached the end | |
tmpArr[tmpCurrentIdx++] = arr[tmpLeftStart++]; // first element in the left side should be used | |
} else if (arr[tmpLeftStart] < arr[tmpRightStart]) { // first on the left side is smaller | |
tmpArr[tmpCurrentIdx++] = arr[tmpLeftStart++] // first element in the left side should be used | |
} else { // first on the right side is smaller | |
tmpArr[tmpCurrentIdx++] = arr[tmpRightStart++] // first element in the right side should be used | |
} | |
} | |
// replace the elements in the original array with the sorted ones | |
for(var j = 0; j < tmpCurrentIdx; j++) { | |
arr[startIdx++] = tmpArr[j]; | |
} | |
} | |
// sort! | |
mergeSort(arr, 0, arr.length - 1) | |
console.log(arr) // => [0,1,2,3,4,5,6,7,8,9] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment