'Runsort' - An Adaptive Mergesort for Prolog

This note describes a novel list-sorting method for Prolog which is stable, has O(n logn) worst-case behaviour and O(n) best-case behaviour. The algorithm is an adaptive variant of bottom-up mergesort using so-called long runs of preexisting order to improve efficiency; accordingly we have called it ‘runsort’. Runsort compares favourably with samsort, and a modification to samsort is suggested.