This change solves the sort_list problem without recursion,
which reduces its memory usage from O(log N) to O(1).
It merges the data in a bottom up fashion, by building sorted
runs of length 1, 2, 4, 8, etc. The sorted runs are put onto
two lists alternatively so that it makes the next iteration of
sorting easier.
It also runs about 40% faster than the previous solution based
on the average run time printed by "make sort_list".
This change solves the sort_list problem without recursion, which reduces its memory usage from O(log N) to O(1).
It merges the data in a bottom up fashion, by building sorted runs of length 1, 2, 4, 8, etc. The sorted runs are put onto two lists alternatively so that it makes the next iteration of sorting easier.
It also runs about 40% faster than the previous solution based on the average run time printed by "make sort_list".