function merge(arr1, arr2) {
    let i = 0;
    let j = 0;
    let sortedArr = [];
    while(i < arr1.length && j < arr2.length) {
        if(arr1[i] < arr2[j]) {
            sortedArr.push(arr1[i]);
            i++;
        } else {
           sortedArr.push(arr2[j]);
           j++; 
        }
    }
    //two while loops incase there is anything left in the arrays after the initial "merge"
    while(i < arr1.length) {
        results.push(arr1[i]);
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j]);
        j++;
    }    
    return sortedArr;
}

function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
}



function mergeIteratively (left, right, leftLimit, rightLimit, sorted, buffer) {
    let i = left;
    
    //Compare the two sub arrays and merge them in the sorted order
    while (left < leftLimit && right < rightLimit) {
      if (sorted[left] <= sorted[right]) {
        buffer[i++] = sorted[left++];
      } else {
        buffer[i++] = sorted[right++];
      }
    }
  
    //If there are elements in the left sub arrray then add it to the result
    while (left < leftLimit) {
      buffer[i++] = sorted[left++];
    }
  
    //If there are elements in the right sub array then add it to the result
    while (right < rightLimit) {
      buffer[i++] = sorted[right++];
    }
  }


  function mergeSortIteratively(arr) {
    //Create two arrays for sorting
    let sorted = Array.from(arr);
    let n = sorted.length;
    let buffer = new Array(n);
    
    for (let size = 1; size < n; size *= 2) {
      for (let leftStart = 0; leftStart < n; leftStart += 2*size) {
        
        //Get the two sub arrays
        let left = leftStart,
            right = Math.min(left + size, n),
            leftLimit = right,
            rightLimit = Math.min(right + size, n);
        
        //Merge the sub arrays
        mergeIteratively(left, right, leftLimit, rightLimit, sorted, buffer);  
      }
      
      //Swap the sorted sub array and merge them
      let temp = sorted;
      sorted = buffer;
      buffer = temp;
    }
    
    return sorted;
  }