Mergesort

Merge sort, also called mergesort, is a divide-and-conquer sorting algorithm. It divides the input into two halves, recursively sorts each half, and merges the two sorted halves into a single sorted sequence. The merge step combines two sorted lists by repeatedly selecting the smallest front element from either list. This approach yields a stable sort and can be implemented on arrays or linked lists.

Time complexity for the standard top-down version is O(n log n) in all cases, while the space requirement is O(n) due to the temporary buffer used during merging. On linked lists, merge sort can be implemented with O(1) extra space by rearranging pointers. Iterative or bottom-up variants begin with small runs and merge them in increasing size, which can improve cache efficiency and avoid recursion overhead. Merge sort is also used as an external sorting method when data is too large to fit in memory, because it processes data in fixed-size blocks and maintains good sequential access patterns.

Applications include stable sorting where preserving the relative order of equal elements matters. It serves as a foundational technique in many algorithms and data processing pipelines, and is a key component of hybrid sorts such as TimSort, which combines insertion sort with merge operations to optimize practical performance. While merge sort has dependable worst-case performance, its memory usage is a consideration compared with in-place sorts in memory-constrained environments.