Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

@raganwald raganwald commented Mar 29, 2015

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
You can’t perform that action at this time.