Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // O(nlogn)
- // Merge two sorted arrays
- const merge = (arr1, arr2) => {
- const sorted = [];
- let i = 0;
- let j = 0;
- // Loop through both arrays and push the greater elements by
- while(i < arr1.length && j < arr2.length) {
- if(arr2[j] > arr1[i]) {
- sorted.push(arr1[i]);
- i++;
- } else {
- sorted.push(arr2[j]);
- j++;
- }
- }
- // Check if there are items left in any of the arrays.
- while(i < arr1.length) {
- sorted.push(arr1[i]);
- i++;
- }
- while(j < arr2.length) {
- sorted.push(arr2[j]);
- j++;
- }
- return sorted;
- }
- const mergeSort = (arr) => {
- // Base case to keep splitting until there is only one item left
- if(arr.length === 1) return arr;
- // Divide array into 2 for merging
- let midIndex = Math.floor(arr.length / 2);
- let left = mergeSort(arr.slice(0, midIndex));
- let right = mergeSort(arr.slice(midIndex));
- // Perform merge on both side
- return merge(left, right)
- }
- console.log(mergeSort([33, 1, 54, 10, 2, 15])); // [ 1, 2, 10, 15, 33, 54 ]
Add Comment
Please, Sign In to add comment