Skip to content

Instantly share code, notes, and snippets.

@raganwald
Last active April 27, 2016 04:38
Show Gist options
  • Save raganwald/0cabc0f8024e8f78ec69 to your computer and use it in GitHub Desktop.
Save raganwald/0cabc0f8024e8f78ec69 to your computer and use it in GitHub Desktop.
Merge Sort in JavaScript
const sorted = arr => {
const length = arr.length;
let unsorted = new Array(length),
sorted = new Array(length);
const destructiveSort = (unsorted, sorted, offset, length) => {
if (length === 1) {
sorted[offset] = unsorted[offset];
}
else if (length > 1) {
const halfLength = Math.floor(length / 2);
destructiveSort(unsorted, sorted, offset, halfLength);
[sorted, unsorted] = destructiveSort(unsorted, sorted, offset + halfLength, length - halfLength);
const z1 = offset + halfLength,
z2 = offset + length;
let i1 = offset,
i2 = offset + halfLength,
i3 = offset;
while (i1 < z1 && i2 < z2) {
if (unsorted[i1] < unsorted[i2]) {
sorted[i3++] = unsorted[i1++];
}
else sorted[i3++] = unsorted[i2++];
}
while (i1 < z1) sorted[i3++] = unsorted[i1++];
while (i2 < z2) sorted[i3++] = unsorted[i2++];
}
return [unsorted, sorted];
}
for (let i = 0; i < length; ++i) unsorted[i] = arr[i];
[unsorted, sorted] = destructiveSort(unsorted, sorted, 0, length)
return sorted;
};
console.log(sorted([]))
console.log(sorted([1]))
console.log(sorted([1, 2]))
console.log(sorted([2, 1]))
console.log(sorted([5, 4, 3, 2, 1]))
const sorted = arr => {
const length = arr.length,
mutableArray = new Array(length),
buffer = new Array(length);
const destructiveSort = (offset, length) => {
// sorting zero or one elements is the degenerate case.
if (length > 1) {
const halfLength = Math.floor(length / 2);
// sort the first and second haves in place
destructiveSort(offset, halfLength);
destructiveSort(offset + halfLength, length - halfLength);
// now merge the two sorted sublists into the buffer
const z1 = offset + halfLength,
z2 = offset + length;
let i1 = offset,
i2 = offset + halfLength,
i3 = offset;
while (i1 < z1 && i2 < z2) {
if (mutableArray[i1] < mutableArray[i2]) {
buffer[i3++] = mutableArray[i1++];
}
else buffer[i3++] = mutableArray[i2++];
}
while (i1 < z1) buffer[i3++] = mutableArray[i1++];
while (i2 < z2) buffer[i3++] = mutableArray[i2++];
// and copy the buffer back to the origial
for (let i = offset; i < z2; ++i) mutableArray[i] = buffer[i];
}
}
for (let i = 0; i < length; ++i) mutableArray[i] = arr[i];
destructiveSort(0, length)
return mutableArray;
};
@raganwald
Copy link
Author

The flip-flop version is more efficient, but the inline version seems simpler to follow.

Comments welcome

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment