Merge Sort Khai

// Merge Sort
void merge(Book catalog[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    // Create temporary arrays
    Book* leftArray = new Book[n1];
    Book* rightArray = new Book[n2];

    // Copy data to temporary arrays leftArray[] and rightArray[]
    for (int i = 0; i < n1; i++)
        leftArray[i] = catalog[left + i];
    for (int j = 0; j < n2; j++)
        rightArray[j] = catalog[middle + 1 + j];

    // Merge the temporary arrays back into catalog[left..right]
    int i = 0;
    int j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i].bookID <= rightArray[j].bookID) {
            catalog[k] = leftArray[i];
            i++;
        }
        else {
            catalog[k] = rightArray[j];
            j++;
            // Increment the total swaps counter for Merge Sort
            totalSwapsMergeSort++;
        }
        k++;
    }

    // Copy the remaining elements of leftArray[], if there are any
    while (i < n1) {
        catalog[k] = leftArray[i];
        i++;
        k++;
    }

    // Copy the remaining elements of rightArray[], if there are any
    while (j < n2) {
        catalog[k] = rightArray[j];
        j++;
        k++;
    }

    // Release allocated memory for temporary arrays
    delete[] leftArray;
    delete[] rightArray;
}

// Merge Sort
void mergeSort(Book catalog[], int left, int right) {
    if (left < right) {
        // Same as (left + right) / 2, but avoids overflow for large left and right
        int middle = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(catalog, left, middle);
        mergeSort(catalog, middle + 1, right);

        // Merge the sorted halves
        merge(catalog, left, middle, right);
    }
}