Figure 1: Pseudocode.
Take unsorted list A of length N Loop through A from start with step size 1 Identify if value X is lowest or highest so far If not lowest or highest entry so far then Loop through A from start with step size N<sup>1/2</sup> Identify if value Y is highest value still lower than X End loop Loop through A from Y with step size 1 Find address in list B of higher value Z Identify if Z is lower than X Set Z to highest value found lower than X End loop Set address in of Z in list B to point to X End if Finish loop Loop through list A Order A into C using values in B Finish loop