Skip to content

Instantly share code, notes, and snippets.

@celwell
Last active January 1, 2019 02:05
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 celwell/d3bc7d7331895371a33c099c8442cacd to your computer and use it in GitHub Desktop.
Save celwell/d3bc7d7331895371a33c099c8442cacd to your computer and use it in GitHub Desktop.
Merge Sort in JavaScript, simple implementation
// 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