Premium
Splaysort: Fast, Versatile, Practical
Author(s) -
Moffat Alistair,
Eddy Gary,
Petersson Ola
Publication year - 1996
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(199607)26:7<781::aid-spe35>3.0.co;2-b
Subject(s) - quicksort , merge sort , computer science , sorting , sorting algorithm , parallel computing , overhead (engineering) , algorithm , sorting network , theoretical computer science , programming language
Adaptivity in sorting algorithms is sometimes gained at the expense of practicality. We give experimental results showing that Splaysort — sorting by repeated insertion into a Splay tree — is a surprisingly efficient method for in‐memory sorting. Splaysort appears to be adaptive with respect to all accepted measures of presortedness, and it outperforms Quicksort for sequences with modest amounts of existing order. Although Splaysort has a linear space overhead, there are many applications for which this is reasonable. In these situations Splaysort is an attractive alternative to traditional comparison‐based sorting algorithms such as Heapsort, Mergesort, and Quicksort.