MergeSort without and with concat

MergeSort 1 - only use 2 additional left and right arrays for merging. MergeSort2 - using slice, concat and additional result array for merging.

by dpnminh

HTML

<div>
<button onclick="mergeSortPerform(1)">
Merge Sort without concat
</button>
<button onclick="mergeSortPerform(2)">
Merge Sort with concat
</button>
</div>

JavaScript

function MergeSort1(A, start, end){
  if (start >= end) return;
  var middle = Math.floor((start + end) / 2);
  MergeSort1(A, start, middle);
  MergeSort1(A, middle + 1, end);
  Merge1(A, start, middle, end);
}

function Merge1(A, start, middle, end){
  var leftArr = [], rightArr = [], leftIndex = 0, rightIndex = 0, i = start;
  
  leftArr = A.slice(start, middle + 1);
  rightArr = A.slice(middle + 1, end + 1);
  
  while (leftIndex <leftArr.length && rightIndex < rightArr.length && i < end + 1){
  	if (leftArr[leftIndex] < rightArr[rightIndex]){
    	A[i] = leftArr[leftIndex];
      leftIndex++;
    }
    else{
    	A[i] = rightArr[rightIndex];
      rightIndex++;
    }
    
    i++;
  }
  
  while (leftIndex <leftArr.length){
  	A[i] = leftArr[leftIndex];
    leftIndex++;
    i++;
  }
  
  while (rightIndex < rightArr.length){
  	A[i] = rightArr[rightIndex];
    rightArr++;
    i++;
  }
}

function mergeSortPerform(type){
	var arr = Array.from({length: 10}, () => Math.floor(Math.random() * 40));
  console.log('before - ', arr);
  
  if (type === 1){
  	MergeSort1(arr, 0, arr.length - 1);
 		console.log('after - ', arr);
  }
  else {
  	arr = MergeSort2(arr);
 		console.log('after - ', arr);
  }
}

function MergeSort2(arr){
  if (arr.length === 1) return arr;
  var middle = Math.floor(arr.length / 2),
      leftArr = arr.slice(0, middle),
      rightArr = arr.slice(middle);
      
  var sortedLeft = MergeSort2(leftArr),
  		sortedRight = MergeSort2(rightArr);
      
  return Merge2(sortedLeft, sortedRight);
}

function Merge2(left, right){
  var 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));
}