...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
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:
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. ...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.