'Runsort' - An Adaptive Mergesort for Prolog

Abstract

This note describes a novel list-sorting method for Prolog which is stable, has O(n log n) 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.