Merge Sort AA Project

void merge(vector<Student>& students, int low, int mid, int high, int& swapCount) {
    // ... (constant time operations)

    for (int i = 0; i < n1; i++)
        left[i] = students[low + i];  // O(n1) - copying elements to left array
    for (int j = 0; j < n2; j++)
        right[j] = students[mid + 1 + j];  // O(n2) - copying elements to right array

    int i = 0, j = 0, k = low;

    while (i < n1 && j < n2) {
        if (left[i].id <= right[j].id) {
            students[k++] = left[i++];  // O(1) - copying element from left to students
        } else {
            students[k++] = right[j++];
            swapCount += n1 - i;  // O(1) - counting swaps when elements are moved from left to right
        }
    }

    while (i < n1) {
        students[k++] = left[i++];  // O(1) - copying remaining elements from left to students
    }
    while (j < n2) {
        students[k++] = right[j++];  // O(1) - copying remaining elements from right to students
    }
}

void mergeSort(vector<Student>& students, int low, int high, int& swapCount) {
    if (low < high) {
        int mid = low + (high - low) / 2;

        mergeSort(students, low, mid, swapCount);   // T(n/2) - recursive call on left half
        mergeSort(students, mid + 1, high, swapCount);  // T(n/2) - recursive call on right half

        merge(students, low, mid, high, swapCount);  // O(n) - merging two sorted halves
    }
    // Base case: if low >= high, no work is done
}