Skip to content

Instantly share code, notes, and snippets.

@friedemannsommer
Created April 3, 2017 12:21
Show Gist options
  • Save friedemannsommer/f1177d0b818362c3c7ce275f98183bf1 to your computer and use it in GitHub Desktop.
Save friedemannsommer/f1177d0b818362c3c7ce275f98183bf1 to your computer and use it in GitHub Desktop.
Javascript merge sort implementation
/* usage example */
console.log(
mergeSort(
[1, 8, 6, 8, 6, 4, 2, 10, 89, 5456, 55],
(a, b) => {
if (a > b) {
return -1
} else if (a < b) {
return 1
}
return 0
}
)
)
/* merge sort implementation */
function mergeSort(list, compareFn) {
if (list.length <= 1) {
return list
}
const length = list.length
const left = []
const right = []
for (let index = 0; index < length; index++) {
if (index < length / 2) {
left.push(list[index])
} else {
right.push(list[index])
}
}
return mergeList(mergeSort(left, compareFn), mergeSort(right, compareFn), compareFn)
}
function mergeList(left, right, compareFn) {
const result = []
let a, b
while (left.length > 0 && right.length > 0) {
a = left[0]
b = right[0]
if (compareFn(a, b) <= 0) {
result.push(a)
left.shift()
} else {
result.push(b)
right.shift()
}
}
while (left.length > 0) {
result.push(left.shift())
}
while (right.length > 0) {
result.push(right.shift())
}
return result
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment