Skip to content

Instantly share code, notes, and snippets.

@monis0395
Last active May 30, 2021 15:06
Show Gist options
  • Save monis0395/d01693a62ce8b643a13cc7cedf477995 to your computer and use it in GitHub Desktop.
Save monis0395/d01693a62ce8b643a13cc7cedf477995 to your computer and use it in GitHub Desktop.
A readable merge sort implementation in JS
Ref: https://en.wikipedia.org/wiki/Merge_algorithm#Merging_two_lists
algorithm merge(A, B) is
inputs A, B : list
returns list
C := new empty list
while A is not empty and B is not empty do
if head(A) ≤ head(B) then
append head(A) to C
drop the head of A
else
append head(B) to C
drop the head of B
// By now, either A or B is empty. It remains to empty the other input list.
while A is not empty do
append head(A) to C
drop the head of A
while B is not empty do
append head(B) to C
drop the head of B
return C
function mergeSort(arr, low, high) {
if (low < high) {
const mid = low + Math.floor((high - low) / 2);
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
function merge(arr, low, mid, high) {
const temp = new Array(high - low + 1);
let c = 0; // temp pointer
let a = low; // list A pointer
let b = mid + 1; // list B pointer
while (a <= mid && b <= high) {
if (arr[a] < arr[b]) {
temp[c++] = arr[a++];
} else {
temp[c++] = arr[b++];
}
}
// By now, either A or B is empty.
// add elements left in the list A
while (a <= mid) {
temp[c++] = arr[a++];
}
// add elements left in the list B
while (b <= high) {
temp[c++] = arr[b++];
}
// copy temp to original list
for(let k = 0; k < temp.length; k++) {
arr[k + low] = temp[k]
}
}
let arr = [ 4, 5, 3, 2, 4, 1 ];
console.log(arr); // [ 4, 5, 3, 2, 4, 1 ]
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [ 1, 2, 3, 4, 4, 5 ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment