Repository: TheAlgorithms/C-Plus-Plus
File: sorting/tim_sort.cpp (C++)

Code before:
    // start merging from size RUN (or 32). It will merge to form size 64, then
    // 128, 256 and so on ....
    for (int size = RUN; size < n; size = 2 * size) {
        // pick starting point of left sub array. We are going to merge
        // arr[left..left+size-1] and arr[left+size, left+2*size-1] After every
        // merge, we increase left by 2*size
        for (int left = 0; left < n; left += 2 * size) {
            // find ending point of left sub array
            // mid+1 is starting point of right sub array
            int mid = std::min((left + size - 1), (n - 1));
            int right = std::min((left + 2 * size - 1), (n - 1));

            // merge sub array arr[left.....mid] & arr[mid+1....right]
            merge(arr, left, mid, right);
        }
    }
}

// utility function to print the Array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

void test(int n) {
    int *arr = new int[n];

    std::iota(arr, arr + n, 0);
    std::reverse(arr, arr + n);
    assert(!std::is_sorted(arr, arr + n));

    timSort(arr, n);
    assert(std::is_sorted(arr, arr + n));

    delete[] arr;
}

// Driver program to test above function
int main() {
    test(65);

    int arr[] = {5, 21, 7, 23, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);

    printf("After Sorting Array is\n");
    printArray(arr, n);
    return 0;

Review comment (suggestion):
```suggestion
    // Case: array of length 65
    int arr[65];
```


Code after:
    // start merging from size RUN (or 32). It will merge to form size 64, then
    // 128, 256 and so on ....
    for (int size = RUN; size < n; size = 2 * size) {
        // pick starting point of left sub array. We are going to merge
        // arr[left..left+size-1] and arr[left+size, left+2*size-1] After every
        // merge, we increase left by 2*size
        for (int left = 0; left < n; left += 2 * size) {
            // find ending point of left sub array
            // mid+1 is starting point of right sub array
            const int mid = std::min((left + size - 1), (n - 1));
            const int right = std::min((left + 2 * size - 1), (n - 1));

            // merge sub array arr[left.....mid] & arr[mid+1....right]
            merge(arr, left, mid, right);
        }
    }
}

// utility function to print the Array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

/**
 * @brief self-test implementation 
 * @returns void
 */
void tests() {
    // Case: array of length 65
    constexpr int N = 65;
    int arr[N];

    std::iota(arr, arr + N, 0);
    std::reverse(arr, arr + N);
    assert(!std::is_sorted(arr, arr + N));

    timSort(arr, N);
    assert(std::is_sorted(arr, arr + N));
}

// Driver program to test above function
int main() {
    tests(); // run self test implementations

    int arr[] = {5, 21, 7, 23, 19};
    const int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);