vadimkorr
3/17/2018 - 5:40 PM

merge-sort

Merge sort

// Merge sort

function mergeSort(vals, scrtach, start, end) {
  if (start == end) return;
  
  let mid = Math.floor((start + end) / 2);
  
  mergeSort(vals, scratch, start, mid);
  mergeSort(vals, scratch, mid + 1, end);

  let leftInd = start;
  let rightInd = mid + 1;
  let scratchInd = leftInd;
  
  while((leftInd <= mid) && (rightInd <= end)) {
    if (vals[leftInd] <= vals[rightInd]) {
      scratch[scratchInd++] = vals[leftInd++];
    } else {
      scratch[scratchInd++] = vals[rightInd++];
    }
  }
  
  for(let i=leftInd; i<=mid; i++) {
    scratch[scratchInd++] = vals[i];
  }
  for(let i=rightInd; i<=end; i++) {
    scratch[scratchInd++] = vals[i];
  }
  for(let i=start; i<=end; i++) {
    vals[i]=scratch[i];
  }
}

let vals = [5, 1, 9, 4, 2, 3, 6, 8, 7];
let scratch = [];
mergeSort(vals, scratch, 0, vals.length-1);
console.log('Result:');
console.log('Vals: ', vals);