Merge sort is an efficient, general-purpose, comparison-based, divide and conquer sorting algorithm.
Merge Sort has a linearithmic time complexity for all possible cases.
Below the implementation of Merge Sort as used on this page.
1export default class MergeSort extends Algorithm {2 name = "Merge Sort"3 timeComplexityBest = Complexities.linearithmic4 timeComplexityAverage = Complexities.linearithmic5 timeComplexityWorst = Complexities.linearithmic67 execute(array: number[]): void {8 this.mergeSort(array)9 }1011 mergeSort(array: number[]): number[] {12 this.incrementOpCounter()13 const len = array.length14 if (len < 2) {15 return array16 }1718 const mid = Math.floor(len / 2)19 const left = array.slice(0, mid)20 const right = array.slice(mid)2122 return this.merge(this.mergeSort(left), this.mergeSort(right))23 }2425 merge(left: number[], right: number[]): number[] {26 const leftLen = left.length27 const rightLen = right.length28 let l = 029 let r = 030 const result = []3132 while (l < leftLen && r < rightLen) {33 this.incrementOpCounter()34 if (left[l] < right[r]) {35 result.push(left[l++])36 } else {37 result.push(right[r++])38 }39 }4041 return result.concat(left.slice(l)).concat(right.slice(r))42 }43}