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; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
The flip-flop version is more efficient, but the inline version seems simpler to follow.
Comments welcome❗