Velocity Reviews > C++ > Exponential tree implementation

Exponential tree implementation

Alec Taylor
Guest
Posts: n/a

 04-17-2012
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...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

Alec Taylor
Guest
Posts: n/a

 04-17-2012
Arghh, ended up making a very n00bish mistake;

On Tuesday, April 17, 2012 5:24:38 PM UTC+10, Alec Taylor wrote:
> 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 2002 paper: "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...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