Null is always sorted.

1 is always sorted.

x, y can always be sorted (and goes in "the second slot" because it's "too big" for "the first slot").

Now you have:

    0: null
    1: [x, y]

When you add another item (z, q, whatever...) you repeat the process until you "blow up" slot[1], and mergesort into "the next doubled big" slot.

    A0: [z]
    A1: [x, y]
    --
    B0: null 
    B1: null
    B2: [q, x, y, z]
    --
    C0: null
    C1: [q, z]
    C2: [x, y]
    --
    D0: [a]
    D1: null
    D2: [q, x, y, z]

...each array (slot) is guaranteed sorted, and is guaranteed binary-searchable.

...each array (slot) is guaranteed sorted, so adjacent slots can be "merge-sorted" into the next slot "for free".

...to understand recursion, you must first understand recursion. ;-)

...the "B" and "C" steps are actually "in error", but hopefully is illustrative that they would both be valid representations and are equivalent from a searching perspective.

Basically, you're paying the pointer-cost (overhead) for log-n "Slots" (heads) making it space-efficient. Dealing _only_ with sub-sorted-arrays means you're always either binary-searching (time-efficient) or merge-sorting (popping previously sorted items from list A or list B), which is also time-efficient.

It's kindof neat b/c (for example) you can get "Z" up at the top when you think it should be "down below", but it doesn't really matter b/c you'll do a binary search in slot 1 (nope, it's not "Z"!), and then binary search down below until you find what you're looking for. When it's "time" for "Z" to move down, it'll move down to the right place "automatically" as you're merging adjacent (sorted) lists.

Maybe think of it as: 1,2,4,8,16, where the slot with 16 entries is always perfectly sorted, but you have the temporary buffers of 1,2,4,8 to be pre-sorting your stuff until you need to bump up to 32 entries.

thank you so much. so its alot like a resizable sorted array that doubles when it gets full, but instead of copying the old one, we keep an array of arrays

Except this one is only locally sorted.

You would have to merge sort sub vectors to get all items in order.

Try the "Interactive visualization" on the page!

Each bucket is either empty or has size 2^k, where k is the index of the bucket (0-based).