Library sort: Difference between revisions

Content deleted Content added
top: in what language was this first written?
Muf99 (talk | contribs)
Pseudocode: Added the rebalancing operations and fixed some of the indexing
Line 38:
'''procedure''' rebalance(A, begin, end) '''is'''
r ← end
w ← end ÷× 2
'''while''' r ≥ begin '''do'''
A[w+1] ← gap
A[w] ← A[r]
A[w+-1] ← gap
r ← r − 1
w ← w − 2
Line 50:
S ← new array of n gaps
'''for''' i ← 1 to floor(log2(n) + -1)) '''do'''
'''for'''rebalance(S, j ← 2^i to1, 2^(i + -1) '''do'''))
'''for''' insjbinarysearch2^(A[j],i-1) S,to 2^(i − 1))'''do'''
ins ← binarysearch(A[j], S, 2^i)
insert A[j] at S[ins]