{{ message }}

Instantly share code, notes, and snippets.

# DonkeyKongJr/MergeSort.js

Last active May 28, 2020
Merge Sort in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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

to join this conversation on GitHub. Already have an account? Sign in to comment