#include <iostream>
using namespace std;

void BubbleSort(int* array, size_t len) {
    for (size_t j = len; j > 0; j--) {
        bool sorted = true;

        for (int i = 1; i < j; i++) {
            if (array[i - 1] > array[i]) {
                swap(array[i - 1], array[i]);
                sorted = false;
            }
        }

        if (sorted) break;
    }
}

void InsertionSort(int* array, size_t len) {
    for (size_t j = 1; j < len; j++) {
        size_t p = j;

        while (p > 0 && array[p - 1] > array[p])
            swap(array[p - 1], array[p]), p--;
    }
}

void SelectionSort(int* array, size_t len) {
    for (int i = 0; i < len; i++) {
        int pos = i;

        for (int j = i + 1; j < len; j++) {
            if (array[j] < array[pos])
                pos = j;
        }

        swap(array[i], array[pos]);
    }
}

void QuickSort(int* array, size_t len) {
    if (len > 1) {
        size_t l = 0, r = len - 1, mid = len >> 1;
        int pivot = array[mid];

        while (l <= r) {
            while (array[l] < pivot) l++;
            while (array[r] > pivot) r--;

            if (l < r)
                swap(array[l++], array[r--]);
            else break;
        }

        QuickSort(array, l);
        QuickSort(array + l, len - l);
    }
}

void HeapSort(int* array, size_t len) {
    // Building the heap
    int* heap = new int[len];

    for (int i = 0; i < len; i++) {
        heap[i] = array[i]; int j = i;

        while (j > 0) {
            int parent = (j - 1) >> 1;

            if (heap[parent] > heap[j])
                swap(heap[parent], heap[j]),
                j = parent;
            else break;
        }
    }

    // Extracting the heap
    for (int i = 0; i < len; i++) {
        array[i] = heap[0]; int j = 0;
        swap(heap[0], heap[len - i - 1]);

        while (true) {
            int  first_child = j * 2 + 1;
            int second_child = j * 2 + 2;

            if (first_child < len - i) {
                int child;

                if (second_child < len - i - 1) {
                    if (heap[first_child] < heap[second_child])
                        child = first_child;
                    else
                        child = second_child;
                } else {
                    if (first_child < len - i - 1)
                        child = first_child;
                    else break;
                }

                if (heap[child] < heap[j]) {
                    swap(heap[child], heap[j]), j = child;
                } else break;
            } else break;
        }
    }

    // Deleting the heap
    delete[] heap;
}

void MergeSort(int* array, size_t len) {
    size_t mid = len >> 1;

    if (len > 1) {
        MergeSort(array, mid);
        MergeSort(array + mid, len - mid);
    }

    int* temp = new int[len];
    int i = 0, j = 0;

    for (int p = 0; p < len; p++) {
        if (i >= mid)
            temp[p] = array[mid + j], j++;
        else if (mid + j >= len)
            temp[p] = array[i], i++;
        else if (array[i] <= array[mid + j])
            temp[p] = array[i], i++;
        else
            temp[p] = array[mid + j], j++;
    }

    for (int p = 0; p < len; p++)
        array[p] = temp[p];

    delete[] temp;
}

void __RadixSort__(int* array, size_t len, int digit) {
    if (len > 1 && digit >= 0) {
        size_t* digit_count = new size_t[256];
        size_t* digit_ptr = new size_t[256];
        int* buffer = new int[len];

        fill(digit_count, digit_count + 256, 0);
        fill(digit_ptr, digit_ptr + 256, 0);

        for (int i = 0; i < len; i++) {
            unsigned char temp = *((unsigned char*) (array + i) + digit);
            digit_count[temp]++;
        }

        for (int i = 1; i < 256; i++)
            digit_ptr[i] = digit_ptr[i - 1] + digit_count[i - 1];

        for (int i = 0; i < len; i++) {
            unsigned char temp = *((unsigned char*) (array + i) + digit);
            buffer[digit_ptr[temp]++] = array[i];
        }

        memcpy(array, buffer, len * sizeof(int));

        for (int i = 0; i < 256; i++) {
            __RadixSort__(array + digit_ptr[i] - digit_count[i], digit_count[i], digit - 1);
        }

        delete[] digit_count;
        delete[] digit_ptr;
        delete[] buffer;
    }
}

void RadixSort(int* array, size_t len) {
    __RadixSort__(array, len, sizeof(int) - 1);
}