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 N1/2
          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