Merge sort

Merge sort (or mergesort) is an divide and conquer algorithm for sorting a list of items. John von Neumann first presented it in 1945. It is similar to quicksort, developed in 1960. The difference is that with merge sort, dividing the lists is trivial, and merging them together isn't. With quicksort, dividing the lists is more complex, but the merging step is trivial.
Usage.
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.