iterative mergesort

iterative_mergesort.js

function mergeSort(array, start, end) {
    if (array.length <= 1) return array;
  
    let slices = []
    let nextSlices = []
    let nextSlicesTemp = []
    let unit = 2 // then 4 then 8 and so on

    const mid = Math.floor((start + end) / 2);
    if(mid + 1 <= end) {
      slices.push({
        start: mid + 1,
        end,
        arr: array.slice(mid + 1, end + 1)
      })
    }
    slices.push({
      start,
      end: mid,
      arr: array.slice(start, mid + 1)
    })

    while(slices.length) {
      const slice = slices.pop()
      if(slice.end > slice.start) {
        const mid = Math.floor((slice.start + slice.end) / 2);
        if(mid + 1 <= slice.end) {
          slices.push({
            start: mid + 1,
            end: slice.end,
            arr: array.slice(mid + 1, slice.end + 1)
          })
        }
        slices.push({
          start: slice.start,
          end: mid,
          arr: array.slice(slice.start, mid + 1)
        })
      }
      
      if(slice.end == slice.start) {
        nextSlices.push(slice)
      }
    }
  
  
    while(nextSlices.length > 1) {
      let max_i = 0
      for(let i = 1; i < nextSlices.length; i += 2) {
        const prev = nextSlices[i-1]
        const curr = nextSlices[i]

        nextSlicesTemp.push({
          start: prev.start,
          end: curr.end,
          arr: merge(prev.arr, curr.arr)
        })
        max_i = i
      }
      
      if(max_i < nextSlices.length) {
        while(max_i+1 < nextSlices.length) {
          nextSlicesTemp.push(nextSlices[++max_i])
        }
      }
  
      nextSlices = nextSlicesTemp
      unit *= 2
      nextSlicesTemp = []
      max_i = 0      
    }
  
    return nextSlices[0].arr
}

function merge(left, right) {
    let result = [], leftIndex = 0, rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}


mergeSort([0,1,2,3,6,5,4,7,8, -1, -3], 0, 10)