A
Alec Taylor
I have become obsessed with improving the bounds for integer sorting after reading; Arne Andersson's 1995 paper: "Faster Deterministic Sorting and Searching in Linear Space"[1], Mikkel Thorup's 1998 paper: "Faster deterministic sorting and priority queues in linear space"[2], Yijie Han's 2002paper: "Deterministic sorting in O(n log log n) time and linear space"[3] and Han & Thorup's 2002 paper: "Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space"[4].
Unfortunately when I got down to implementing the "Exponential search tree"data-structure of Andersson I ran into some trouble.
I think I mis-implemented the insert function.
Where did I go wrong? - http://ideone.com/F1T1f
Thanks for all suggestions,
Alec Taylor
[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7109
[2]: http://dl.acm.org/citation.cfm?id=314844
[3]: http://dl.acm.org/citation.cfm?id=975984
[4]: http://dl.acm.org/citation.cfm?id=645413.652131
Unfortunately when I got down to implementing the "Exponential search tree"data-structure of Andersson I ran into some trouble.
I think I mis-implemented the insert function.
Where did I go wrong? - http://ideone.com/F1T1f
Thanks for all suggestions,
Alec Taylor
[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7109
[2]: http://dl.acm.org/citation.cfm?id=314844
[3]: http://dl.acm.org/citation.cfm?id=975984
[4]: http://dl.acm.org/citation.cfm?id=645413.652131