Content deleted Content added
remove reference to web resource that in turn cites Wikipedia per WP:COPYWITHIN |
→Implementation: add pseudocode |
||
Line 43:
3. Re-Balancing:
Inserting spaces between each pair of elements in the array.
because there are log n rounds in the algorithm, total re-balancing takes
O(n log n) time only.
===Pseudocode===
'''proc''' rebalance(A, begin, end)
r ← end
w ← end * 2
'''while''' r >= begin
A[w+1] ← gap
A[w] ← A[r]
r ← r - 1
w ← w - 2
'''proc''' sort(A)
n ← length(A)
S ← new array of n gaps
'''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]
===C-Implementation===
| |||