For code that implements a merge sort or a significant part of it

Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list.

Conceptually, a pure 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.

It is also possible to make a hybrid merge sort that does not divide into n single-element sublists. Instead, it can choose a larger threshold and sort the smallest sublists with a different sorting method (e.g. insertion sort). This is done because merge sort has a relatively high overhead. For small lists, a quadratic sort can be quicker.

Merge sort is a loglinear time sorting method in average and worst case. This compares well to heap sort and quicksort. For sufficiently large data, it is faster than quadratic sorts like insertion sort and bubble sort.