Library sort: Difference between revisions

Revision as of 04:30, 19 January 2016

Revision as of 11:40, 7 May 2016

Line 65:

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

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

ins ← binarysearch(A[j], 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, to find a place where to locate element A[j]. Insertion should favor gaps over filled-in elements.

== References ==