#merge-sort

Merge sort is a sorting algorithm that has a worst case complexity of $\mathcal{O}(n\lg n)$. Merge sort is often the typical example for divide and conquer algorithm. The merge sort consists of two parts, the merge algorithm and the merge-sort algorithm.

Merge Given two sorted lists, merge both of them to into a newly created sorted list.

Merge Algorithm

Mergesort Partition an array into two and call the merge sort of the two partitioned array, then merge both of them.