How does A-sort work?

Question

Could someone please shed some light on the workings of A-sort (not asort()), which uses (a,b)-trees for sorting partially sorted sequences?

Answer 1

The algorithm itself is pretty simple - basically you insert all the elements in the tree, then traverse the tree to read the elements in order.

To get better performance for almost already sorted sequences, it uses the following modifications:

1. The tree must be an (a,b) tree with b>2a-1, that has O(1) amortized insert rebalancing time.
2. The tree contains links to siblings of nodes on the same level (across the whole tree)

To leverage the O(1) insert time, you just have to quickly find the place the next element belongs, assuming the sequence is nearly sorted (so it won't be far from where the previous element inserted). This is done roughly as follows:

• you start at the previous element inserted
• you check if the next element doesn't belong to this node or any subtree of this node; if not, you look at the siblings (let's say the new element is smaller so it would be the left sibling)
• if the sibling's values are still too large, you go up one level and repeat
• if the new element belongs to the sibling's subtrees, you do a normal search down from there
• if the new element belongs between the sibling and this node, you go to the leftest child and repeat the search going down until you find the proper subtree

This way, you can go traverse a^k elements of the tree in k steps, therefore, it will take you O(log(distance(current, previous)) time to find the proper place for the new element. Given amortized O(1) rebalancing, you get better than O(n log n) time for almost sorted sequences, while maintaining O(n log n) worst-case.