Create a gist now

Instantly share code, notes, and snippets.

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
Owner

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