Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

(“Merge Sort” 2022)

Merge sort is:

Algorithm

procedure MergeSort(list) is
  if length of list <= 1 then
    return list

  left, right = split(list)
  MergeSort(left)
  MergeSort(right)

  return Merge(left, right)

Implementation

Complexity

Worst-caseBest-case
Time\(O(n \operatorname{log}(n))\)\(O(n \operatorname{log}(n))\)
Space\(O(n)\)\(O(n)\)

Bibliography

“Merge Sort.” 2022. Wikipedia, June. https://en.wikipedia.org/w/index.php?title=Merge_sort&oldid=1095865966.