Skip to content

Big O Visualizer

Merge Sort

Merge sort is an efficient, general-purpose, comparison-based, divide and conquer sorting algorithm.

Complexity

Merge Sort has a linearithmic time complexity for all possible cases.

Algorithm

Below the implementation of Merge Sort as used on this page.

src/algorithms/merge-sort.ts
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}