Merge Sort

Introduction

Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

How does it work?

In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.

/*
*  A: Input array
*  B: Output array
*  lo: lower bound
*  hi: upper bound
*  off: offset
*/

algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1

    if len == 1 then
        B[off] := A[lo]

    else let T[1..len] be a new array
        mid := (lo + hi) / 2
        mid' := mid - lo + 1

        fork parallelMergesort(A, lo, mid, T, 1)

        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Step By Step

Implementation (JavaScript)

mergeSort(values) {
  let leftIndex = 0;
  let rightIndex = values.length - 1;
  this.sort(values, leftIndex, rightIndex);
}

sort(values, leftIndex, rightIndex) {
  if (leftIndex >= rightIndex) return;

  const middleIndex = Math.trunc((leftIndex + rightIndex) / 2);

  this.sort(values, leftIndex, middleIndex);
  this.sort(values, middleIndex + 1, rightIndex);
  this.merge(values, leftIndex, middleIndex, rightIndex);
}

merge(values, leftIndex, middleIndex, rightIndex) {
  const lArrayLength = middleIndex - leftIndex + 1;
  const rArrayLength = rightIndex - middleIndex;

  const lArray = [];
  const rArray = [];

  for (let i = 0; i < lArrayLength; i++)
    lArray[i] = values[leftIndex + i];

  for (let i = 0; i < rArrayLength; i++)
    rArray[i] = values[(middleIndex + 1) + i];

  let lArrayIndex = 0;
  let rArrayIndex = 0;
  let mergedArrayIndex = leftIndex;
	
  while(lArrayIndex < lArrayLength && rArrayIndex < rArrayLength) {
    if (lArray[lArrayIndex] <= rArray[rArrayIndex]) {
      values[mergedArrayIndex] = lArray[lArrayIndex];
      lArrayIndex++;
    }
		
    else {
      values[mergedArrayIndex] = rArray[rArrayIndex];
      rArrayIndex++;
    }

    mergedArrayIndex++;
  }

  while(lArrayIndex < lArrayLength) {
    values[mergedArrayIndex] = lArray[lArrayIndex];
    lArrayIndex++;
    mergedArrayIndex++;
  }	

  while(rArrayIndex < rArrayLength) {
    values[mergedArrayIndex] = rArray[rArrayIndex];
    rArrayIndex++;
    mergedArrayIndex++;
  }
}

Merge Sort

Introduction

How does it work?

Step By Step

Implementation (JavaScript)

Visualization