before sorting. By permuting the input, the algorithm becomes
insensitive to the input sequence, which by definition,
LIBRARY SORT is not an adaptive algorithm that
can take advantage of a nearly sorted sequence. Under the
incremental sorting model, input comes individually, permuting
the future input is impossible. With the incremental
sorting model, without the permutation of input and
with adversary insertion (such as reverse sorted order that
can happen fairly often in real life scenarios), the performance
of this algorithm degrades to amortized
(pn) operations
per insertion, regardless of the . This makes the
worst case O(n1:5) operations, although it might be possible
to improve the runtime cost to worst case amortized
O(lg2 n) per insertion (Bender et al. 2002). Although in
their assumptions the time bound is amortized per insertion,
regardless of the disorder of the input sequence, as
their algorithm needs to rebalance the gaps on the 2i-th
insertion.