Skip to content

Instantly share code, notes, and snippets.

@ivarprudnikov
Created February 7, 2021 13:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ivarprudnikov/0617c3ba4e2cf6abaaad0dd48f2cf459 to your computer and use it in GitHub Desktop.
Save ivarprudnikov/0617c3ba4e2cf6abaaad0dd48f2cf459 to your computer and use it in GitHub Desktop.
Merge sort in javascript
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