Exponential tree implementation

From	Alec Taylor <alec.taylor6@gmail.com>
Newsgroups	comp.lang.c++
Subject	Exponential tree implementation
Date	2012-04-17 00:24 -0700
Organization	http://groups.google.com
Message-ID	<16199152.641.1334647478254.JavaMail.geo-discussion-forums@pbjk8> (permalink)

Show all headers | View raw

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

Back to comp.lang.c++ | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Exponential tree implementation Alec Taylor <alec.taylor6@gmail.com> - 2012-04-17 00:24 -0700
  Re: Exponential tree implementation Alec Taylor <alec.taylor6@gmail.com> - 2012-04-17 00:47 -0700

csiph-web