Library sort, lub Sortowanie biblioteczne to algorytm sortowania , który bazuje na algorytmie sortowania przez wstawianie , ale z dodaniem pustych miejsc w tablicy w celu przyśpieszenie wstawiania elementów. Nazwa wywodzi się z następującej analogii:

Wyobraźmy sobie bibliotekarza, który układa książki alfabetycznie na półkach. Zaczynając od książek na literę A ustawia jedną przy drugiej, aż dojdzie do litery Z. Jeśli bibliotekarz postanowi dodać nową książkę na półkę, której nazwa zaczyna się na literę B, to będzie musiał przesunąć wszystkie książki od miejsca, gdzie pasuje nowa książka aż do ostatniej książki. Ponieważ litera B występuje blisko początku alfabetu, więc praktycznie całą półkę książek należy przesunąć. W celu przyśpieszenia pracy bibliotekarz powinien zostawiać wolne miejsce po każdej książce i wówczas może wstawić jedną nową książkę na półkę bez przesuwania. Na tym polega algorytm Sortowania bibliotecznego.^[]

Algorytm zaproponował 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 log n) (podobnie jak algorytmu quicksort ), rzadziej O(n²) (jak przy sortowaniu przez wstawianie). Mankamentem algorytmu jest zwiększone zapotrzebowanie na pamięć.

Bibliografia

• Original publication at Citeseer