Last active
January 1, 2019 02:05
-
-
Save celwell/d3bc7d7331895371a33c099c8442cacd to your computer and use it in GitHub Desktop.
Merge Sort in JavaScript, simple implementation
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
// helper fn used by merge_sort; merges two arrays into sorted order | |
var merge = function (left, right) { | |
let merged = [], | |
i = 0, // left array index counter | |
j = 0; // right array index counter | |
while (i < left.length && j < right.length) { | |
if (left[i] < right[j]) { | |
merged.push(left[i]); | |
i++; | |
} else { | |
merged.push(right[j]); | |
j++; | |
} | |
} | |
// append any remaining elements | |
if (i < left.length) { | |
merged = merged.concat(left.slice(i - left.length)); | |
} else if (j < right.length) { | |
merged = merged.concat(right.slice(j - right.length)); | |
} | |
return merged; | |
} | |
// O(nlogn) Merge Sort algorithm | |
var merge_sort = function (arr) { | |
if (arr.length > 1) { | |
let left_size = Math.floor(arr.length / 2), | |
right_size = arr.length - left_size; | |
let left = arr.slice(0, left_size); | |
let right = arr.slice(right_size * -1); | |
return merge(merge_sort(left), merge_sort(right)); | |
} else { | |
return arr; | |
} | |
}; | |
// example input: console.log(merge_sort([15, 25, 24, 0, -4, 4, 5, 3, 2, 3, 1, 27])); | |
// example output: [-4, 0, 1, 2, 3, 3, 4, 5, 15, 24, 25, 27] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment