library sort Algorithm

library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions. Compared to basic insertion sort, the drawback of library sort is that it necessitates extra space for the gaps.

library sort source code, pseudocode and analysis

Insertion: insert the component in the position found and swapping the following components by 1 position till an empty space is hit. This takes linear time, and because there are log N rounds in the algorithm