Library sort: Difference between revisions

Revision as of 13:47, 30 December 2013

Revision as of 14:04, 30 December 2013

Line 63:

'''for''' i ← 1 to floor(log2(n) + 1)

'''for''' j ← 2^i to 2^(i+1)

ins ← binarysearch(S[:, 2^(i-1)])

insert A[j] at S[ins]

Here, <code>binarysearch(A, k)</code> performs [[binary search]] in the first {{mvar|k}} elements of {{mvar|A}}, skipping over gaps. Insertion should favor gaps over filled-in elements.

== References ==