🧰 Developer’s toolbox: ⚥ Merge Sort

Merge Sort.

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.

Wikipedia says:

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4…) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). It is also easily applied to lists, not only arrays, as it only requires sequential access, not random access. However, it has additional O(n) space complexity, and involves a large number of copies in simple implementations.

Github repo: link.

There are two different implementations: top-down and bottom-up; code below is a top-down implementation.

Swift

MergeSort.swift

TypeScript

MergeSort.ts

Output

Merge Sort Output.

Merge.

P.S. We would be happy to see comments according to mistakes & typos.