[TODO] OOP Ass 5 - Merge Sort and Templates

//  OOP Assignment 5

#include <iostream>
using namespace std;

template <class T>
class Sort {
private:
    int size;
    T *arr;
public:
    Sort(int size) {
        this->size = size;
        arr = new T[size];
    }

    ~Sort() {
        delete[] arr;
    }

    void populate(){
        for (int i = 0; i < size; i++) {
            cin >> arr[i];
        }
    }

    void selectSort(){
        T temp;
        int min;
        for (int i = 0; i < size; i++){
            min = i;
            for (int j = i + 1; j < size; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

    void merge(int left, int right, int mid) {
        int s1 = mid - left + 1;
        int s2 = right - mid;

        if (s1 <= 0 || s2 < 0) {
                    cerr << "Error: Invalid array sizes for merging." << endl;
                    return;
            }

        T *L = new T[s1];
        T *R = new T[s2];

        for (int i = 0; i < s1; i++) L[i] = arr[left + i];
        for (int j = 0; j < s2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < s1 and j < s2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < s1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < s2) {
            arr[k] = R[j];
            j++;
            k++;
        }

        delete[] L;
        delete[] R;
    }

    void mergeSort(int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(left, mid);
        mergeSort((mid + 1), right);
        merge(left, mid, right);
    }



    void display() {
        // cout << "\nSorted Array: " << endl;
        cout << "[ ";
        for (int i = 0; i < size; i++) {
            if (i != size - 1) {
                cout << arr[i] << ", ";
            } else if (i == size - 1) {
                cout << arr[i] << " ]";
            }

        }
        cout << endl;
    }
};


int main() {

    int choice;

    while (true) {
        cout << "\n---------- MENU ----------" << endl;
        cout << "1. Sort Integer Values"  << endl;
        cout << "2. Sort Float Values" << endl;
        cout << "3. Exit" << endl;
        cout << "---------------------------" << endl;
        cout << "Enter your choice: "; cin >> choice;
        cout << endl;

        if (choice == 1) {
            int size;
            cout << "Enter the number of elements: "; cin >> size;
            Sort<int> zuck(size);
            zuck.populate();
            cout << "\nThe Entered Array is: " << endl;
            zuck.display();
            //zuck.selectSort();
            zuck.mergeSort(0, size - 1);
            cout << "\nThe Sorted Array is: " << endl;
            zuck.display();
        }

        else if (choice == 2) {
            int size;
            cout << "Enter the number of elements: "; cin >> size;
            Sort<float> zuck(size);
            zuck.populate();
            cout << "\nThe Entered Array is: " << endl;;
            zuck.display();
            //zuck.selectSort();
            zuck.mergeSort(0, size - 1);
            cout << "\nThe Sorted Array is: " << endl;
            zuck.display();

        }

        else if (choice == 3) {
            cout << endl;
            cout << "Terminating program..." << endl;
            cout << "Byee" << endl;
            cout << endl;
            break;
        }

        else {
            cout << endl;
            cout << "ERROR! Please Enter a Valid Choice." << endl;
            cout << endl;
        }
    }




    return 0;
}