| 2 | #include <iostream> |
| 3 | |
| 4 | void librarySort(int *index, int n) { |
| 5 | int lib_size, index_pos, |
| 6 | *gaps, // gaps |
| 7 | *library[2]; // libraries |
| 8 | |
| 9 | bool target_lib, *numbered; |
| 10 | |
| 11 | for (int i = 0; i < 2; i++) |
| 12 | library[i] = new int[n]; |
| 13 | |
| 14 | gaps = new int[n + 1]; |
| 15 | numbered = new bool[n + 1]; |
| 16 | |
| 17 | lib_size = 1; |
| 18 | index_pos = 1; |
| 19 | target_lib = 0; |
| 20 | library[target_lib][0] = index[0]; |
| 21 | |
| 22 | while (index_pos < n) { |
| 23 | // binary search |
| 24 | int insert = std::distance( |
| 25 | library[target_lib], |
| 26 | std::lower_bound(library[target_lib], |
| 27 | library[target_lib] + lib_size, index[index_pos])); |
| 28 | |
| 29 | // if there is no gap to insert a new index ... |
| 30 | |
| 31 | if (numbered[insert] == true) { |
| 32 | int prov_size = 0, next_target_lib = !target_lib; |
| 33 | |
| 34 | // update library and clear gaps |
| 35 | |
| 36 | for (int i = 0; i <= n; i++) { |
| 37 | if (numbered[i] == true) { |
| 38 | library[next_target_lib][prov_size] = gaps[i]; |
| 39 | prov_size++; |
| 40 | numbered[i] = false; |
| 41 | } |
| 42 | |
| 43 | if (i <= lib_size) { |
| 44 | library[next_target_lib][prov_size] = |
| 45 | library[target_lib][i]; |
| 46 | prov_size++; |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | target_lib = next_target_lib; |
| 51 | lib_size = prov_size - 1; |
| 52 | } else { |
| 53 | numbered[insert] = true; |
| 54 | gaps[insert] = index[index_pos]; |
| 55 | index_pos++; |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | int index_pos_for_output = 0; |
| 60 | for (int i = 0; index_pos_for_output < n; i++) { |
| 61 | if (numbered[i] == true) { |