STFC Website

part of UK Research & Innovation

Version 1.0.0

21st September 2007

HSL_KB22: Sorting reals using the Heapsort method

HSL_KB22 is a suite of Fortran 95 procedures for successively arranging a set of real numbers, \(a _1 , a _2 ,..., a _n\), in order of increasing size using the Heapsort method of J. W. J. Williams. At the \(k\)-th stage of the method the \(k\)-th smallest member of the set is found. The method is particularly appropriate if it is not known in advance how many smallest members of the set will be required as the Heapsort method is able to calculate the \(k+\)1st smallest member of the set efficiently once it has determined the first \(k\) smallest members. The method is guaranteed to sort all \(n\) numbers in \(O (n \log n)\) operations. If a complete sort is required, the Quicksort algorithm, KB05, may be preferred.