JAVASCRIPT

merge sort javascript

let array = [70, 50, 30, 10, 20, 40, 60]

function mergeSort(array) {
    let l = 0
    let r = array.length
    let m = Math.round((r - l) / 2)

    if (r === 1) {
        return   // returns recursively
    }

    let L = []   // left half of current array
    let R = []   // right half of current array

    for (let i = l; i < m; i++) {
        L.push(array[i])
    }
    for (let j = m; j < r; j++) {
        R.push(array[j])
    }

    mergeSort(L)
    mergeSort(R)

    let i = 0, j = 0, k = 0

    // Merging part
    while (i < L.length && j < R.length) {
        if (L[i] < R[j]) {
            array[k] = L[i]
            i++
        } else {
            array[k] = R[j]
            j++
        }
      
        k++
    }

    while (i < L.length) {
        array[k] = L[i]
        i++
        k++
    }

    while (j < R.length) {
        array[k] = R[j]
        j++
        k++
    }
}

mergeSort(array)
console.log(array)	 // [Log]: [10, 20, 30, 40, 50, 60, 70]

// Time complexity of merge sort is O(NlogN)
// Space complexity is N, because we use an auxiliary array to sort all elements

merge sort function in JavaScript

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  if (arr.length > 1) {
    const mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid, arr.length);
    return Merge(mergeSort(left), mergeSort(right));
  }
}

function Merge(left, right) {
  let i = 0;
  let j = 0;
  let k = 0;
  let arr = [];
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      arr[k] = left[i];
      i++;
    } else {
      arr[k] = right[j];
      j++;
    }
    k++;
  }
  while (i < left.length) {
    arr[k] = left[i];
    i++;
    k++;
  }
  while (j < right.length) {
    arr[k] = right[j];
    j++;
    k++;
  }
  return arr;
}
let arr = [8, 4, 20, 45, 1 ,29]
console.log(mergeSort(arr));

Merge sort javascript

// Implementation of the merge sort algorithm.
// Let n be size of list to sort.
// Time complexity: O(n log2(n))
// Space complexity: O(n)

function mergeSort(array) {
  if (array.length <= 1) return array;
  mergeSortHelper(array, 0, array.length - 1);
  return array;
}

// Sort the array recursively
function mergeSortHelper(array, leftIdx, rightIdx) {
  // Base case: no more recursive calls needed
  if (rightIdx <= leftIdx) return;
  const middleIdx = Math.floor(leftIdx + (rightIdx - leftIdx) / 2);
  // Recursive step for sorting half of current array
  mergeSortHelper(array, leftIdx, middleIdx);
  mergeSortHelper(array, middleIdx + 1, rightIdx);
  // Merge recursively sorted subarrays
  merge(array, leftIdx, middleIdx, middleIdx + 1, rightIdx);
}

// Merge sorted subarrays
function merge(array, left, leftEnd, right, rightEnd) {
  const sizeSortedArray = rightEnd - left + 1;
  const sortedArray = [];
  let leftIdx = left,
    rightIdx = right;
  let sortedArrayIdx = 0;
  // Always get smaller value from sorted subarrays
  while (leftIdx <= leftEnd && rightIdx <= rightEnd) {
    if (array[leftIdx] < array[rightIdx]) {
      sortedArray[sortedArrayIdx++] = array[leftIdx++];
    } else {
      sortedArray[sortedArrayIdx++] = array[rightIdx++];
    }
  }
  // Get remaining elements if any
  while (leftIdx <= leftEnd) {
    sortedArray[sortedArrayIdx++] = array[leftIdx++];
  }
  // Get remaining elements if any
  while (rightIdx <= rightEnd) {
    sortedArray[sortedArrayIdx++] = array[rightIdx++];
  }
  // Copy sorted version of array back to original array
  arrayCopy(sortedArray, 0, array, left, sizeSortedArray);
}

function arrayCopy(srcArray, srcIndex, destArray, destIndex, length) {
  destArray.splice(
    destIndex,
    length,
    ...srcArray.slice(srcIndex, srcIndex + length)
  );
}

Merge Sort Algorithm in javascript

function mergeSortedAlgo(array) {
    if(array.length <= 1) return array;

    let midPoint = Math.floor(array.length / 2);
    let leftArray = mergeSortedAlgo(array.slice(0, midPoint));
    let rightArray = mergeSortedAlgo(array.slice(midPoint));

    return mergeSortedArray(leftArray, rightArray);
}