#algorithm #sort

idea

Divide and conquer sorting algorithm. Produces stable sort. Most efficient if data to be sorted can only be sorted sequentially.

Non recursive

1. Split list into lists of 1 elements
2. Merge lists two by two by taking the smallest element of the first elements of each two lists.
3. Repeat 2. till only one list is left

Recursive

1. Call mergeSort(a) = mergeSort(mergeSort(a[1], a[n/2-1]), mergeSort(a[n/2], a[n])

Worst case is $O(n \times log(n))$

links

Quick sort

references

https://en.wikipedia.org/wiki/Merge_sort

https://www.geeksforgeeks.org/merge-sort/

recursive implementation

function mergeSortRec(array, start, finish) {
  if (start === finish) {
    return [array[start]]
  }
  const mid = Math.round((start + finish) / 2)
  const firstHalf = mergeSortRec(array, start, mid - 1)
  const secondHalf = mergeSortRec(array, mid, finish)
  const res = []
  while (firstHalf.length > 0 || secondHalf.length > 0) {
    if (secondHalf.length === 0 || (!(firstHalf.length === 0) && firstHalf[0] < secondHalf[0])) {
      res.push(firstHalf.shift())
    } else {
      res.push(secondHalf.shift())
    }
  }
  return res
}

function mergeSort(array) {
  return mergeSortRec(array, 0, array.length - 1)
}