{{ message }}

Instantly share code, notes, and snippets.

# DonkeyKongJr/MergeSort.js

Last active May 28, 2020
Merge Sort in JavaScript
 const mergeSort = (unsortedArray) => { // Check if the length is lower or equal to 1, otherwise return input. // This is also our break condition for the recursion if (unsortedArray.length <= 1) { return unsortedArray; } // Split input array in two equally parts when possible. // The half of the length could possibly be an floating number 3 / 2 = 1.5, // so we use Math.floor to get an whole number by remove the decimal part. const middleIndex = Math.floor(unsortedArray.length / 2); const leftArray = unsortedArray.slice(0, middleIndex); const rightArray = unsortedArray.slice(middleIndex); // Use recursion on the left and right part to break it down return mergeParts(mergeSort(leftArray), mergeSort(rightArray)); }; const mergeParts = (leftArray, rightArray) => { let mergedArray = []; let leftIndex = 0; let rightIndex = 0; // Compare left and right items as long as there is a counterpart (index is not out of range). while (leftIndex < leftArray.length && rightIndex < rightArray.length) { if (leftArray[leftIndex] < rightArray[rightIndex]) { mergedArray.push(leftArray[leftIndex]); leftIndex++; } else { mergedArray.push(rightArray[rightIndex]); rightIndex++; } } // Because there could be some items left on the left or right side we concat all remaining elements. // In theory there should only be one side affected. return mergedArray .concat(leftArray.slice(leftIndex)) .concat(rightArray.slice(rightIndex)); };

### DonkeyKongJr commented May 28, 2020

 You can find more details in this blog post