library sort Algorithm
The library sort algorithm, also known as gapped insertion sort, is an efficient sorting algorithm that combines the principles of insertion sort and binary search to achieve an average-case performance of O(n log n). It was developed by Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro in 2002. This algorithm is particularly suitable for sorting large data sets, as it works by creating gaps or empty spaces between the elements in the array, which reduces the need for shifting elements during the insertion process. The main idea behind library sort is to maintain a sorted list with gaps, so that when a new element needs to be inserted, it can be placed directly into its correct position without having to move many other elements.
The library sort algorithm works in two main phases: insertion and rebalancing. During the insertion phase, elements are inserted into the array one at a time, using binary search to find the correct position for the new element. If a suitable gap is available, the element is placed directly into that gap; otherwise, the element is inserted in the nearest gap, and a local rebalance is performed to maintain the desired density of gaps. The rebalancing phase occurs when there are no more gaps available for insertion. In this phase, the algorithm redistributes the elements and gaps evenly throughout the array, thus allowing for more insertions. After the rebalancing phase, the insertion phase resumes, continuing the process until all elements have been sorted.
#include <algorithm>
#include <iostream>
void librarySort(int *index, int n) {
int lib_size, index_pos,
*gaps, // gaps
*library[2]; // libraries
bool target_lib, *numbered;
for (int i = 0; i < 2; i++)
library[i] = new int[n];
gaps = new int[n + 1];
numbered = new bool[n + 1];
lib_size = 1;
index_pos = 1;
target_lib = 0;
library[target_lib][0] = index[0];
while (index_pos < n) {
// binary search
int insert = std::distance(
library[target_lib],
std::lower_bound(library[target_lib],
library[target_lib] + lib_size, index[index_pos]));
// if there is no gap to insert a new index ...
if (numbered[insert] == true) {
int prov_size = 0, next_target_lib = !target_lib;
// update library and clear gaps
for (int i = 0; i <= n; i++) {
if (numbered[i] == true) {
library[next_target_lib][prov_size] = gaps[i];
prov_size++;
numbered[i] = false;
}
if (i <= lib_size) {
library[next_target_lib][prov_size] =
library[target_lib][i];
prov_size++;
}
}
target_lib = next_target_lib;
lib_size = prov_size - 1;
} else {
numbered[insert] = true;
gaps[insert] = index[index_pos];
index_pos++;
}
}
int index_pos_for_output = 0;
for (int i = 0; index_pos_for_output < n; i++) {
if (numbered[i] == true) {
// std::cout << gaps[i] << std::endl;
index[index_pos_for_output] = gaps[i];
index_pos_for_output++;
}
if (i < lib_size) {
// std::cout << library[target_lib][i] << std::endl;
index[index_pos_for_output] = library[target_lib][i];
index_pos_for_output++;
}
}
}
int main() {
// ---example--
int index_ex[] = {-6, 5, 9, 1, 9, 1, 0, 1, -8, 4, -12};
int n_ex = sizeof(index_ex) / sizeof(index_ex[0]);
librarySort(index_ex, n_ex);
std::cout << "sorted array :" << std::endl;
for (int i = 0; i < n_ex; i++)
std::cout << index_ex[i] << " ";
std::cout << std::endl;
/* --output--
sorted array :
-12 -8 -6 0 1 1 1 4 5 9 9
*/
}
