Re: [math-fun] clumpy heapsort tree

It turns out the clumpy layout is a particular example of what's called the "Van Emde Boas layout." Here's a Google Books reference, including a nice illustration: http://tinyurl.com/emdeboas "Split the tree in the middle, at height h/2. This breaks the tree into a top recursive subtree of height floor(h/2) and several bottom subtrees of height ceil(h/2). There are sqrt(N) bottom subtrees, each of size sqrt(N)." Algorithms using recursively-divided layouts (or access patterns) to take advantage of caches, without knowing the characteristics of the caches in advance, are called "cache-oblivious," and there seems to have been work about cache-oblivious heapsorts. --Steve