Exponential tree implementation

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
 
A

Alec Taylor

Arghh, ended up making a very n00bish mistake;
`tree.insert(i);`, instead of: `tree.insert(inputVector);`
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top