Library sort: Difference between revisions

Revision as of 13:42, 17 December 2019

Revision as of 18:05, 25 December 2019

Line 36:

'''procedure''' rebalance(A, begin, end) '''is'''

r ← end

w ← end *÷ 2

'''while''' r ≥ begin '''do'''

A[w+1] ← gap

A[w] ← A[r]

r ← r -− 1

w ← w -− 2

'''procedure''' sort(A) '''is'''

n ← length(A)

S ← new array of n gaps

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

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

ins ← binarysearch(A[j], S, 2^(i- − 1))

insert A[j] at S[ins]