File MergeSort.h

↰ Parent directory (ADS/sort)

Merge Sort (section 2.7.3): the two halves of the vector are sorted recursively and merged by Merge() through a vector B allocated once, :math:` T( n ) = 2 T( n / 2 ) + Theta( n ) = Theta( n log n ) ` time, optimal among the sorts by comparisons, :math:` Theta( n ) ` extra space, stable (an item of the left part goes first when equal).

Definition (ADS/sort/MergeSort.h)

Detailed Description

When the right part runs out first, the rest of the left one is copied; when the left one does, the rest of the right one is already in place.

  • mergeSort( A , cutoff ) sorts the parts of at most cutoff items with insertionSort(), which is faster on few items (section 2.8);

  • mergeSortBottomUp() merges the runs of length 1 , 2 , 4 , … with no recursion and no stack (exercise 12.5);

  • mergeSort( L ) sorts a LIST with pointers in O( n log n ) by splitting it in two halves, sorting them and merging them (exercise 12.1), only through the operations of the SEQUENCE: each item is copied once per level of the recursion, since the abstract data type moves no cells from a list to another;

  • countInversions() counts the pairs i < j with A[ i ] > A[ j ]: when the merge takes A[ j ] from the right part, it is smaller than all the mid - i + 1 items left in the left part (exercise 12.3).

The contracts [see File Contract.h]: mergeParts() needs start <= mid < end < n, a buffer B as large as A and two sorted halves, the latter an audit; mergeSortRec() needs start <= end < n and cutoff >= 1; the sorts end with the same items sorted, an audit. The functions are defined in MergeSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 2.7.3, https://algoritmicamente.it/materiali/libro/capitoli/cap02.pdf

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 5.2.4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions