Institutions | About Us | Help | Gaeilge
rian logo


Mark
Go Back
'Runsort' - An Adaptive Mergesort for Prolog
BRADY, MICHAEL HAYES
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.
Keyword(s): Prolog
Publication Date:
2005
Type: Report
Peer-Reviewed: No
Language(s): English
Institution: Trinity College Dublin
Citation(s): Brady, Mike , 'Runsort' - An Adaptive Mergesort for Prolog, Dublin, TCD Computer Science Department, March 31, 2005, 2005, (TCD-CS-2005-34)
Publisher(s): TCD Computer Science Department
File Format(s): application/pdf
First Indexed: 2014-05-13 05:26:56 Last Updated: 2015-04-10 05:50:26