Sortowanie biblioteczne

Szablon:Algorytm infobox Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów.

Nazwa wywodzi się z następującej analogii: Szablon:Cytat

Algorytm zaproponowali: Michael A. Bender, Martín Farach-Colton oraz Miguel Mosteiro w 2004 roku. Podobnie jak sortowanie przez wstawianie, na którym bazuje, sortowanie biblioteczne jest algorytmem stabilnym. Wykazano, że jego złożoność czasowa wynosi najczęściej $O(n\cdot \log (n))$ (podobnie jak algorytmu quicksort), rzadziej $O(n^2)$ (jak przy sortowaniu przez wstawianie). Mankamentem algorytmu jest zwiększone zapotrzebowanie na pamięć.