Merge sort

Merge sort (or mergesort) is a divide and conquer algorithm for sorting a list of items. Merge sort is a stable sorting algorithm, while quicksort is not. It has a worst-case complexity of O(n*log(n)). Merge sort is also highly parallelizable. It can be used for solving the inversion counting problem.