SHARE
TWEET

Untitled

a guest Feb 16th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // O(nlogn)
  2. // Merge two sorted arrays
  3. const merge = (arr1, arr2) => {
  4.     const sorted = [];
  5.     let i = 0;
  6.     let j = 0;
  7.  
  8.     // Loop through both arrays and push the greater elements by
  9.     while(i < arr1.length && j < arr2.length) {
  10.         if(arr2[j] > arr1[i]) {
  11.             sorted.push(arr1[i]);
  12.             i++;
  13.         } else {
  14.             sorted.push(arr2[j]);
  15.             j++;
  16.         }
  17.     }
  18.  
  19.     // Check if there are items left in any of the arrays.
  20.     while(i < arr1.length) {
  21.         sorted.push(arr1[i]);
  22.         i++;
  23.     }
  24.     while(j < arr2.length) {
  25.         sorted.push(arr2[j]);
  26.         j++;
  27.     }
  28.    
  29.     return sorted;
  30. }
  31.  
  32. const mergeSort = (arr) => {
  33.     // Base case to keep splitting until there is only one item left
  34.     if(arr.length === 1) return arr;
  35.     // Divide array into 2 for merging
  36.     let midIndex =  Math.floor(arr.length / 2);
  37.     let left =  mergeSort(arr.slice(0, midIndex));
  38.     let right = mergeSort(arr.slice(midIndex));
  39.  
  40.     // Perform merge on both side
  41.     return merge(left, right)
  42. }
  43.  
  44. console.log(mergeSort([33, 1, 54, 10, 2, 15])); // [ 1, 2, 10, 15, 33, 54 ]
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top