How to implement merge sort in JavaScript?

Posted by Prem Tiwari | Updated on January 17, 2020

In this answer, I have shared how to implement merge sort in JavaScript.

Merge Sort Algorithm

Divide the unsorted list into n sublists, each containing one element. A list of one element is inherently sorted.
Repeatedly merge sorted sublists (called “runs”) to produce longer runs until there is only one run remaining. This is the sorted list.

Example: Merge sort in JavaScript

<html>

<body>

function mSort (array) {

if (array.length === 1) {

return array

}

const middle = Math.floor(array.length / 2)

const left = array.slice(0, middle)

const right = array.slice(middle)

document.write(middle);

return merge(

mSort(left),

mSort(right)

)

}

// compare the arrays item by item and return the concatenated result

function merge (left, right) {

let result = []

let leftIndex = 0

let rightIndex = 0

while (leftIndex < left.length && rightIndex < right.length) {

if (left[leftIndex] < right[rightIndex]) {

result.push(left[leftIndex])

leftIndex++

document.write("</br>");

} else {

result.push(right[rightIndex])

rightIndex++

}

return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))

}

const list = [4,7,5,9,1,3,8,2]

document.write(mSort(list));

</script>

</body>

</html>

If you like this question & answer and want to contribute, then write your question & answer and email to freewebmentor[@]gmail.com. Your question and answer will appear on FreeWebMentor.com and help other developers.

How to implement merge sort in JavaScript?

Merge Sort Algorithm

Related Questions & Answers

Solved Programs