#ifndef SORT_H
#define SORT_H

#include "Array.h"
#include "Object.h"

namespace Kylin {

class Sort : public Object {
public:
    template <typename T>
    static void select(T array[], size_t size) {
        for (size_t i = 0; i < size; i++) {
            size_t index = i;
            for (size_t j = i + 1; j < size; j++) {
                if (array[j] < array[index]) index = j;
            }
            if (index != i) swap(array[i], array[index]);
        }
    }

    template <typename T>
    static void insert(T array[], int size) {
        for (int i = 1; i < size; i++) {
            T value = array[i];
            int index = i;
            for (int j = i - 1; j >= 0; j--) {
                if (value < array[j]) {
                    array[j + 1] = array[j];
                    index = j;
                } else
                    break;
            }
            if (index != i) array[index] = value;
        }
    }

    template <typename T>
    static void bubble(T array[], int size) {
        bool swaped = true;
        for (int i = 0; (i < size) && swaped; i++) {
            swaped = false;
            for (int j = size - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    swap(array[j], array[j - 1]);
                    swaped = true;
                }
            }
        }
    }

    template <typename T>
    static void shell(T array[], size_t size) {
        size_t gap = size;
        do {
            gap = gap / 3 + 1;
            for (size_t i = 0; i < size; i += gap) {
                size_t index = i;
                for (size_t j = i + gap; j < size; j++) {
                    if (array[j] < array[index]) {
                        index = j;
                    }
                }
                if (index != i) swap(array[index], array[i]);
            }

        } while (gap > 1);
    }

    template <typename T>
    static void quick(T array[], size_t size) {
        quick(array, 0, size - 1);
    }

    template <typename T>
    static void merge(T array[], size_t size) {
        T *helper = new T[size];
        merge(array, helper, 0, size - 1);
        delete[] helper;
    }

protected:
    template <typename T>
    static void merge(T array[], T helper[], size_t begin, size_t end) {
        if (begin >= end) return;
        size_t middle = (begin + end) / 2;
        merge(array, helper, begin, middle);
        if (middle < end) merge(array, helper, middle + 1, end);
        merge(array, helper, begin, middle, end);
    }

    template <typename T>
    static void merge(T array[], T helper[], size_t begin, size_t middle, size_t end) {
        size_t i = begin, j = middle + 1, k = begin;
        while ((i <= middle) && (j <= end)) {
            if (array[i] < array[j]) {
                helper[k++] = array[i++];
            } else {
                helper[k++] = array[j++];
            }
        }
        while (i <= middle) {
            helper[k++] = array[i++];
        }
        while (j <= end) {
            helper[k++] = array[j++];
        }

        for (size_t i = begin; i <= end; i++) {
            array[i] = helper[i];
        }
    }

    template <typename T>
    static void quick(T array[], size_t begin, size_t end) {
        if (begin >= end) return;
        auto pivot = partition(array, begin, end);
        if (pivot > 0) quick(array, begin, pivot - 1);
        quick(array, pivot + 1, end);
    }

    template <typename T>
    static size_t partition(T array[], size_t begin, size_t end) {
        T value = array[begin];
        while (begin < end) {
            while ((begin < end) && (array[end] > value)) {
                end--;
            }
            swap(array[begin], array[end]);
            while ((begin < end) && (array[begin] <= value)) {
                begin++;
            }
            swap(array[begin], array[end]);
        }
        return begin;
    }

    template <typename T>
    static void swap(T &a, T &b) {
        T c(a);
        a = b;
        b = c;
    }

    Sort() = delete;
    Sort(const Sort &) = delete;
    Sort &operator=(const Sort &) = delete;
};
} // namespace Kylin

#endif // SORT_H