AlgoDaily - Merge Sort vs. Quick Sort vs. Heap Sort

Home > Data Structures and Algorithms 🚀 > Pointers and Windows > Merge Sort vs. Quick Sort vs. Heap Sort

The merge sort can be implemented using the two functions described below.

merge_sort(array, startIndex, lastIndex)
merge(array, startIndex, middle, lastIndex)

Here, in the merge function, we will merge two sub-arrays. One sub-array has a range from start to middlewhile the other will go from middle+1 to the last index. We will divide the array into sub-arrays on the merge_sort function.

An implementation of the MergeSort algorithm has been provided below:

xxxxxxxxxx
console.log(mergeSort([5, 4, 3, 2, 1]));
 
function merge(leftArr, rightArr) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;
​
  // Sort parts
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      resultArray.push(leftArr[leftIndex]);
      leftIndex++; // move left array cursor
    } else {
      resultArray.push(rightArr[rightIndex]);
      rightIndex++; // move right array cursor
    }
  }
​
  // There will be one element remaining from either left or the right
  // Concat to account for it
  return resultArray
          .concat(leftArr.slice(leftIndex))
          .concat(rightArr.slice(rightIndex));
}
​
function mergeSort(unsortedArr) {
  // Only one element base case
  if (unsortedArr.length <= 1) {
    return unsortedArr;
  }
​
  // Determine midpoint
  const midIdx = Math.floor(unsortedArr.length / 2);

Programming Categories

Popular Lessons