square_sort.cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Mart Molle's Square Sorting algorithm

// Time Complexity: O(n^2), Theta(n^2), Omega(n)
// Space Complexity: O(1)
template <typename T>
void insertion_sort(vector<T>& v, int root_begin, int root_end) {
        int hole_index;
        int j;
        for (int i = root_begin + 1; i < root_end; i++) {
                j = i;  
                while (j > 0 && v.at(j) < v.at(j - 1)) {
                        swap(v.at(j), v.at(j - 1));
                        --j;
                }
        }
};

// Time Complexity: O(n^2), Theta(n^2), Omega(n^2)
// Space Complexity: O(1)
template <typename T>
void selection_sort(vector<T>& v, int root_begin, int root_end) {
        int min_index;

        for (int i = root_begin; i < root_end; i++) {
                min_index = i;
                for (int j = i + 1; j < root_end; j++) {
                        if (v.at(j) < v.at(min_index)) {
                                min_index = j;
                        }
                }
                swap(v.at(i), v.at(min_index));
        }
};

// Time Complexity: O(n*sqrt(n))
template <typename T>
void square_sort(vector<T>& v) {
        int root_begin = 0;
        int root_end = sqrt(v.size());
        int root = root_end;
        
        while (root_begin < v.size()) {
                insertion_sort(v, root_begin, root_end);
                root_begin += root;
                root_end += root;
        }
        selection_sort(v, 0, v.size());
}
template <typename T>
void print(vector<T>& v) {
        for (auto i : v) {
                cout << i << " ";
        }
        cout << endl;
}
int main() {
        vector<int> unsorted{50,2,1,4,6,8,9,1,20,21,23,17};

        print(unsorted);
        square_sort(unsorted);
        print(unsorted);

        return 0;
}