The story
By analogy with a librarian who leaves gaps between books so that inserting a new book does not require moving so many of the existing books.
Etymology from Wiktionary, CC BY-SA 4.0.
library sort
Today it means: A form of insertion sort that leaves gaps between elements to accelerate subsequent insertions. Full definition →