Big O Visualizer

1export default class MergeSort extends Algorithm {
2  name = "Merge Sort"
3  timeComplexityBest = Complexities.linearithmic
4  timeComplexityAverage = Complexities.linearithmic
5  timeComplexityWorst = Complexities.linearithmic
6
7  execute(array: number[]): void {
8    this.mergeSort(array)
9  }
10
11  mergeSort(array: number[]): number[] {
12    this.incrementOpCounter()
13    const len = array.length
14    if (len < 2) {
15      return array
16    }
17
18    const mid = Math.floor(len / 2)
19    const left = array.slice(0, mid)
20    const right = array.slice(mid)
21
22    return this.merge(this.mergeSort(left), this.mergeSort(right))
23  }
24
25  merge(left: number[], right: number[]): number[] {
26    const leftLen = left.length
27    const rightLen = right.length
28    let l = 0
29    let r = 0
30    const result = []
31
32    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    }
40
41    return result.concat(left.slice(l)).concat(right.slice(r))
42  }
43}