PDMerge is short for Pattern-Defeating Mergesort. It is a O(n)
best case time, O(n log n)
worst-case, and O(n)
space complexity. It is a runs-adaptive algorithm and it comes in three variants.
This repo contains implementations of PDMerge and its variants in various programming languages. The reference C implementatoin can be found in the "C" folder.
The base algorithm will collect as many runs as absolutely possible. It uses n / 2
external records and (n + 3) / 2
external indices.
This will use insertion sort on runs less that 16 elements in length. It uses n / 2
external records and (n + 31) / 16
external indices.
This will use a pair of binary searches to copy as little data to external arrays as possible per merge. It uses n / 2
external records and (n + 31) / 16
external indices.
This will use up to 24 extra threads to split the load of merging. It uses n
external records and (n + 31) / 16
external indices.