5、排序算法

#include <iostream>
#include <vector>

using namespace std;

void beadSort(vector<int>& arr) {
    int n = arr.size();
    int maxElem = arr[0];

    // 找到数组中最大的元素
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxElem) {
            maxElem = arr[i];
        }
    }

    // 初始化一个二维数组来表示小珠子的位置
    vector<vector<int>> beads(maxElem, vector<int>(n));

    // 将每个元素表示为一列小珠子，并将它们放置在杆子上
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < arr[i]; j++) {
            beads[j][i] = 1;
        }
    }

    // 让小珠子根据重力向下滑动，直到落到最下面的位置
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < maxElem; j++) {
            if (beads[j][i] == 1) {
                sum++;
                beads[j][i] = 0;
            } else if (sum > 0) {
                beads[j][i] = 1;
                sum--;
            }
        }
    }

    // 从杆子底部向上读取每个元素的值，得到有序的结果
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = maxElem - 1; j >= 0; j--) {
            if (beads[j][i] == 1) {
                sum++;
            } else if (sum > 0) {
                arr[i] = sum;
                break;
            }
        }
    }
}

int main() {
    vector<int> arr = {5, 3, 1, 4, 2};
    beadSort(arr);

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

// C++ program to implement gravity/bead sort
#include <cstdio>
#include <cstring>

#define BEAD(i, j) beads[i * max + j]

// function to perform the above algorithm
void beadSort(int *a, int len) {
    // Find the maximum element
    int max = a[0];
    for (int i = 1; i < len; i++)
        if (a[i] > max)
            max = a[i];

    // allocating memory
    unsigned char *beads = new unsigned char[max * len];
    memset(beads, 0, static_cast<size_t>(max) * len);

    // mark the beads
    for (int i = 0; i < len; i++)
        for (int j = 0; j < a[i]; j++) BEAD(i, j) = 1;

    for (int j = 0; j < max; j++) {
        // count how many beads are on each post
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += BEAD(i, j);
            BEAD(i, j) = 0;
        }

        // Move beads down
        for (int i = len - sum; i < len; i++) BEAD(i, j) = 1;
    }

    // Put sorted values in array using beads
    for (int i = 0; i < len; i++) {
        int j;
        for (j = 0; j < max && BEAD(i, j); j++) {
        }

        a[i] = j;
    }
    delete[] beads;
}

// driver function to test the algorithm
int main() {
    int a[] = {5, 3, 1, 7, 4, 1, 1, 20};
    int len = sizeof(a) / sizeof(a[0]);

    beadSort(a, len);

    for (int i = 0; i < len; i++) printf("%d ", a[i]);

    return 0;
}

void bitonicSort(vector<int>& arr, int low, int count, bool isAscending) {
    if (count > 1) {
        int k = count / 2;

        // 比特位单调递增排序
        bitonicSort(arr, low, k, true);

        // 比特位单调递减排序
        bitonicSort(arr, low + k, k, false);

        // 比特位合并
        bitonicMerge(arr, low, count, isAscending);
    }
}

void bitonicMerge(vector<int>& arr, int low, int count, bool isAscending) {
    if (count > 1) {
        int k = count / 2;
        for (int i = low; i < low + k; i++) {
            if (isAscending == (arr[i] > arr[i + k])) {
                swap(arr[i], arr[i + k]);
            }
        }
        bitonicMerge(arr, low, k, isAscending);
        bitonicMerge(arr, low + k, k, isAscending);
    }
}

void bitonicSort(vector<int>& arr) {
    int n = arr.size();
    bitonicSort(arr, 0, n, true);
}

// Source : https://www.geeksforgeeks.org/bitonic-sort/

/* C++ Program for Bitonic Sort. Note that this program
   works only when size of input is a power of 2. */

#include <algorithm>
#include <iostream>

/*The parameter dir indicates the sorting direction, ASCENDING
   or DESCENDING; if (a[i] > a[j]) agrees with the direction,
   then a[i] and a[j] are interchanged.*/
void compAndSwap(int a[], int i, int j, int dir) {
    if (dir == (a[i] > a[j]))
        std::swap(a[i], a[j]);
}

/*It recursively sorts a bitonic sequence in ascending order,
  if dir = 1, and in descending order otherwise (means dir=0).
  The sequence to be sorted starts at index position low,
  the parameter cnt is the number of elements to be sorted.*/
void bitonicMerge(int a[], int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2;
        for (int i = low; i < low + k; i++) compAndSwap(a, i, i + k, dir);
        bitonicMerge(a, low, k, dir);
        bitonicMerge(a, low + k, k, dir);
    }
}

/* This function first produces a bitonic sequence by recursively
    sorting its two halves in opposite sorting orders, and then
    calls bitonicMerge to make them in the same order */
void bitonicSort(int a[], int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2;

        // sort in ascending order since dir here is 1
        bitonicSort(a, low, k, 1);

        // sort in descending order since dir here is 0
        bitonicSort(a, low + k, k, 0);

        // Will merge wole sequence in ascending order
        // since dir=1.
        bitonicMerge(a, low, cnt, dir);
    }
}

/* Caller of bitonicSort for sorting the entire array of
   length N in ASCENDING order */
void sort(int a[], int N, int up) { bitonicSort(a, 0, N, up); }

// Driver code
int main() {
    int a[] = {3, 7, 4, 8, 6, 2, 1, 5};
    int N = sizeof(a) / sizeof(a[0]);

    int up = 1;  // means sort in ascending order
    sort(a, N, up);

    std::cout << "Sorted array: \n";
    for (int i = 0; i < N; i++) std::cout << a[i] << " ";
    return 0;
}

#include <algorithm>
#include <random>

using namespace std;

bool isSorted(vector<int>& arr) {
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

void bogoSort(vector<int>& arr) {
    while (!isSorted(arr)) {
        random_shuffle(arr.begin(), arr.end());
    }
}

/**
 * @file
 * @brief Implementation of [Bogosort algorithm](https://en.wikipedia.org/wiki/Bogosort)
 *
 * @details
 *      In computer science, bogosort (also known as permutation sort, stupid sort, slowsort, 
 *      shotgun sort, random sort, monkey sort, bobosort or shuffle sort) is a highly inefficient 
 *      sorting algorithm based on the generate and test paradigm. Two versions of this algorithm 
 *      exist: a deterministic version that enumerates all permutations until it hits a sorted one,
 *      and a randomized version that randomly permutes its input.Randomized version is implemented here. 
 *
 * ### Algorithm
 * Shuffle the array untill array is sorted.
 *
 * @author [Deep Raval](https://github.com/imdeep2905)
 */
#include <iostream>
#include <algorithm>
#include <array>
#include <cassert>


/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {
/**
 * Function to shuffle the elements of an array. (for reference)
 * @tparam T typename of the array
 * @tparam N length of array
 * @param arr array to shuffle
 * @returns new array with elements shuffled from a given array
 */
template <typename T, size_t N>
std::array <T, N> shuffle (std::array <T, N> arr) {
    for (int i = 0; i < N; i++) {
        // Swaps i'th  index with random index (less than array size)
        std::swap(arr[i], arr[std::rand() % N]);
    }
    return arr;
}
/**
 * Implement randomized Bogosort algorithm and sort the elements of a given array.
 * @tparam T typename of the array
 * @tparam N length of array
 * @param arr array to sort
 * @returns new array with elements sorted from a given array
 */
template <typename T, size_t N>
std::array <T, N> randomized_bogosort (std::array <T, N> arr) {
    // Untill array is not sorted
    while (!std::is_sorted(arr.begin(), arr.end())) {
        std::random_shuffle(arr.begin(), arr.end());// Shuffle the array
    }
    return arr;
}

}  // namespace sorting

/**
 * Function to display array on screen 
 * @tparam T typename of the array
 * @tparam N length of array
 * @param arr array to display
 */
template <typename T, size_t N>
void show_array (const std::array <T, N> &arr) {
    for (int x : arr) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

/**
 * Function to test above algorithm
 */
void test() {
    // Test 1
    std::array <int, 5> arr1;
    for (int &x : arr1) {
        x = std::rand() % 100;
    }
    std::cout << "Original Array : ";
    show_array(arr1);
    arr1 = sorting::randomized_bogosort(arr1);
    std::cout << "Sorted Array : ";
    show_array(arr1);
    assert(std::is_sorted(arr1.begin(), arr1.end()));
    // Test 2
    std::array <int, 5> arr2;
    for (int &x : arr2) {
        x = std::rand() % 100;
    }
    std::cout << "Original Array : ";
    show_array(arr2);
    arr2 = sorting::randomized_bogosort(arr2);
    std::cout << "Sorted Array : ";
    show_array(arr2);
    assert(std::is_sorted(arr2.begin(), arr2.end()));
}

/** Driver Code */
int main() {
    // Testing
    test();
    // Example Usage
    std::array <int, 5> arr = {3, 7, 10, 4, 1}; // Defining array which we want to sort
    std::cout << "Original Array : ";
    show_array(arr);
    arr = sorting::randomized_bogosort(arr); // Callling bogo sort on it
    std::cout << "Sorted Array : ";
    show_array(arr); // Printing sorted array
    return 0;
}

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

/**
 * @file
 * @brief Bubble sort algorithm
 *
 * The working principle of the Bubble sort algorithm:

Bubble sort algorithm is the bubble sorting algorithm. The most important reason
for calling the bubble is that the largest number is thrown at the end of this
algorithm. This is all about the logic. In each iteration, the largest number is
expired and when iterations are completed, the sorting takes place.

What is Swap?

Swap in the software means that two variables are displaced.
An additional variable is required for this operation. x = 5, y = 10.
We want x = 10, y = 5. Here we create the most variable to do it.

int z;
z = x;
x = y;
y = z;

The above process is a typical displacement process.
When x assigns the value to x, the old value of x is lost.
That's why we created a variable z to create the first value of the value of x,
and finally, we have assigned to y.

Bubble Sort Algorithm Analysis (Best Case - Worst Case - Average Case)

Bubble Sort Worst Case Performance is O (n²). Why is that? Because if you
remember Big O Notation, we were calculating the complexity of the algorithms in
the nested loops. The n * (n - 1) product gives us O (n²) performance. In the
worst case all the steps of the cycle will occur. Bubble Sort (Avarage Case)
Performance. Bubble Sort is not an optimal algorithm. in average, O (n²)
performance is taken. Bubble Sort Best Case Performance. O (n). However, you
can't get the best status in the code we shared above. This happens on the
optimized bubble sort algorithm. It's right down there.
*/

#include <iostream>
#include <vector>

int main() {
    int n;
    bool swap_check = true;
    std::cout << "Enter the amount of numbers to sort: ";
    std::cin >> n;
    std::vector<int> numbers;
    std::cout << "Enter " << n << " numbers: ";
    int num;

    // Input
    for (int i = 0; i < n; i++) {
        std::cin >> num;
        numbers.push_back(num);
    }

    // Bubble Sorting
    for (int i = 0; (i < n) && (swap_check); i++) {
        swap_check = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (numbers[j] > numbers[j + 1]) {
                swap_check = true;
                std::swap(numbers[j],
                          numbers[j + 1]);  // by changing swap location.
                                            // I mean, j. If the number is
                                            // greater than j + 1, then it
                                            // means the location.
            }
        }
    }

    // Output
    std::cout << "\nSorted Array : ";
    for (int i = 0; i < numbers.size(); i++) {
        if (i != numbers.size() - 1) {
            std::cout << numbers[i] << ", ";
        } else {
            std::cout << numbers[i] << std::endl;
        }
    }
    return 0;
}

void bucketSort(vector<int>& arr, int bucketSize) {
    if (arr.empty()) {
        return;
    }

    int minValue = arr[0];
    int maxValue = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }

    int bucketCount = (maxValue - minValue) / bucketSize + 1;
    vector<vector<int>> buckets(bucketCount);

    for (int i = 0; i < arr.size(); i++) {
        int bucketIndex = (arr[i] - minValue) / bucketSize;
        buckets[bucketIndex].push_back(arr[i]);
    }

    arr.clear();
    for (int i = 0; i < bucketCount; i++) {
        sort(buckets[i].begin(), buckets[i].end());
        for (int j = 0; j < buckets[i].size(); j++) {
            arr.push_back(buckets[i][j]);
        }
    }
}

// C++ program to sort an array using bucket sort
#include <algorithm>
#include <iostream>
#include <vector>

// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n) {
    // 1) Create n empty buckets
    std::vector<float> *b = new std::vector<float>[n];

    // 2) Put array elements in different buckets
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i];  // Index in bucket
        b[bi].push_back(arr[i]);
    }

    // 3) Sort individual buckets
    for (int i = 0; i < n; i++) std::sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++) arr[index++] = b[i][j];
    delete[] b;
}

/* Driver program to test above funtion */
int main() {
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);

    std::cout << "Sorted array is \n";
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    return 0;
}

void cocktailSelectionSort(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int minIndex = left;
        int maxIndex = right;

        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }

        swap(arr[left], arr[minIndex]);

        if (maxIndex == left) {
            maxIndex = minIndex;
        }

        swap(arr[right], arr[maxIndex]);

        left++;
        right--;
    }
}

// Returns Sorted elements after performing Cocktail Selection Sort
// It is a Sorting algorithm which chooses the minimum and maximum element in an
// array simultaneously, and swaps it with the lowest and highest available
// position iteratively or recursively

#include <algorithm>
#include <iostream>
#include <vector>

// Iterative Version

void CocktailSelectionSort(std::vector<int> *vec, int low, int high) {
    while (low <= high) {
        int minimum = (*vec)[low];
        int minimumindex = low;
        int maximum = (*vec)[high];
        int maximumindex = high;

        for (int i = low; i <= high; i++) {
            if ((*vec)[i] >= maximum) {
                maximum = (*vec)[i];
                maximumindex = i;
            }
            if ((*vec)[i] <= minimum) {
                minimum = (*vec)[i];
                minimumindex = i;
            }
        }
        if (low != maximumindex || high != minimumindex) {
            std::swap((*vec)[low], (*vec)[minimumindex]);
            std::swap((*vec)[high], (*vec)[maximumindex]);
        } else {
            std::swap((*vec)[low], (*vec)[high]);
        }

        low++;
        high--;
    }
}

// Recursive Version

void CocktailSelectionSort_v2(std::vector<int> *vec, int low, int high) {
    if (low >= high)
        return;

    int minimum = (*vec)[low];
    int minimumindex = low;
    int maximum = (*vec)[high];
    int maximumindex = high;

    for (int i = low; i <= high; i++) {
        if ((*vec)[i] >= maximum) {
            maximum = (*vec)[i];
            maximumindex = i;
        }
        if ((*vec)[i] <= minimum) {
            minimum = (*vec)[i];
            minimumindex = i;
        }
    }
    if (low != maximumindex || high != minimumindex) {
        std::swap((*vec)[low], (*vec)[minimumindex]);
        std::swap((*vec)[high], (*vec)[maximumindex]);
    } else {
        std::swap((*vec)[low], (*vec)[high]);
    }

    CocktailSelectionSort(vec, low + 1, high - 1);
}

// main function, select any one of iterative or recursive version

int main() {
    int n;
    std::cout << "Enter number of elements\n";
    std::cin >> n;
    std::vector<int> v(n);
    std::cout << "Enter all the elements\n";
    for (int i = 0; i < n; ++i) {
        std::cin >> v[i];
    }

    int method;
    std::cout << "Enter method: \n\t0: iterative\n\t1: recursive:\t";
    std::cin >> method;

    if (method == 0) {
        CocktailSelectionSort(&v, 0, n - 1);
    } else if (method == 1) {
        CocktailSelectionSort_v2(&v, 0, n - 1);
    } else {
        std::cerr << "Unknown method" << std::endl;
        return -1;
    }
    std::cout << "Sorted elements are\n";
    for (int i = 0; i < n; ++i) {
        std::cout << v[i] << " ";
    }

    return 0;
}

void combSort(vector<int>& arr) {
    int n = arr.size();
    int gap = n;
    bool swapped = true;

    while (gap > 1 || swapped) {
        gap = gap * 10 / 13;
        if (gap < 1) {
            gap = 1;
        }

        swapped = false;
        for (int i = 0; i < n - gap; i++) {
            if (arr[i] > arr[i + gap]) {
                swap(arr[i], arr[i + gap]);
                swapped = true;
            }
        }
    }
}

/**
 *
 * \file
 * \brief [Comb Sort Algorithm
 * (Comb Sort)](https://en.wikipedia.org/wiki/Comb_sort)
 *
 * \author
 *
 * \details
 * - A better version of bubble sort algorithm
 * - Bubble sort compares adjacent values whereas comb sort uses gap larger
 *   than 1
 * - Best case Time complexity O(n)
 *   Worst case Time complexity O(n^2)
 *
 */

#include <algorithm>
#include <cassert>
#include <iostream>

/**
 *
 * Find the next gap by shrinking the current gap by shrink factor of 1.3
 * @param gap current gap
 * @return new gap
 *
 */
int FindNextGap(int gap) {
    gap = (gap * 10) / 13;

    return std::max(1, gap);
}

/** Function to sort array
 *
 * @param arr array to be sorted
 * @param l start index of array
 * @param r end index of array
 *
 */
void CombSort(int *arr, int l, int r) {
    /**
     *
     * initial gap will be maximum and the maximum possible value is
     * the size of the array that is n and which is equal to r in this
     * case so to avoid passing an extra parameter n that is the size of
     * the array we are using r to initialize the initial gap.
     *
     */
    int gap = r;

    /// Initialize swapped as true to make sure that loop runs
    bool swapped = true;

    /// Keep running until gap = 1 or none elements were swapped
    while (gap != 1 || swapped) {
        /// Find next gap
        gap = FindNextGap(gap);

        swapped = false;

        /// Compare all elements with current gap
        for (int i = l; i < r - gap; ++i) {
            if (arr[i] > arr[i + gap]) {
                std::swap(arr[i], arr[i + gap]);
                swapped = true;
            }
        }
    }
}

void tests() {
    /// Test 1
    int arr1[10] = {34, 56, 6, 23, 76, 34, 76, 343, 4, 76};
    CombSort(arr1, 0, 10);
    assert(std::is_sorted(arr1, arr1 + 10));
    std::cout << "Test 1 passed\n";

    /// Test 2
    int arr2[8] = {-6, 56, -45, 56, 0, -1, 8, 8};
    CombSort(arr2, 0, 8);
    assert(std::is_sorted(arr2, arr2 + 8));
    std::cout << "Test 2 Passed\n";
}

/** Main function */
int main() {
    /// Running predefined tests
    tests();

    /// For user interaction
    int n;
    std::cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; ++i) std::cin >> arr[i];
    CombSort(arr, 0, n);
    for (int i = 0; i < n; ++i) std::cout << arr[i] << ' ';
    delete[] arr;
    return 0;
}

long long merge(vector<int>& arr, int start, int mid, int end) {
    int leftIndex = start;
    int rightIndex = mid + 1;
    vector<int> temp(end - start + 1);
    long long count = 0;
    int index = 0;

    while (leftIndex <= mid && rightIndex <= end) {
        if (arr[leftIndex] <= arr[rightIndex]) {
            temp[index++] = arr[leftIndex++];
        } else {
            temp[index++] = arr[rightIndex++];
            count += mid - leftIndex + 1;
        }
    }

    while (leftIndex <= mid) {
        temp[index++] = arr[leftIndex++];
    }

    while (rightIndex <= end) {
        temp[index++] = arr[rightIndex++];
    }

    for (int i = start; i <= end; i++) {
        arr[i] = temp[i - start];
    }

    return count;
}

long long countInversions(vector<int>& arr, int start, int end) {
    if (start >= end) {
        return 0;
    }

    int mid = start + (end - start) / 2;

    long long count = 0;
    count += countInversions(arr, start, mid);
    count += countInversions(arr, mid + 1, end);
    count += merge(arr, start, mid, end);

    return count;
}

long long countInversionsSort(vector<int>& arr) {
    return countInversions(arr, 0, arr.size() - 1);
}

/**
 * @file
 * @brief Counting Inversions using [Merge
 Sort](https://en.wikipedia.org/wiki/Merge_sort)
 *
 * @details
 * Program to count the number of inversions in an array
 * using merge-sort.
 *
 * The count of inversions help to determine how close the array
 * is to be sorted in ASCENDING order.
 *
 * two elements a[i] and a[j] form an inversion if `a[i]` > `a[j]` and i < j
 *
 * Time Complexity --> `O(n.log n)`

 * Space Complexity --> `O(n)` ; additional array `temp[1..n]`
 * ### Algorithm

 *   1. The idea is similar to merge sort, divide the array into two equal or
 almost
 *      equal halves in each step until the base case is reached.
 *   2. Create a function merge that counts the number of inversions when two
 halves of
 *      the array are merged, create two indices i and j, i is the index for
 first half
 *      and j is an index of the second half. if `a[i]` is greater than `a[j]`,
 then there are (mid – i)
 *      inversions, Because left and right subarrays are sorted, so all the
 remaining elements
 *      in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
 *   3. Create a recursive function to divide the array into halves and find the
 answer by summing
 *      the number of inversions is the first half, number of inversion in the
 second half and
 *      the number of inversions by merging the two.
 *   4. The base case of recursion is when there is only one element in the
 given half.
 *   5. Print the answer
 *
 * @author [Rakshit Raj](https://github.com/rakshitraj)
 */
#include <cassert>   /// for assert
#include <cstdint>   /// for typedef datatype uint64_t
#include <iostream>  /// for IO operations
#include <vector>    /// for std::vector

/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {
/**
 * @namespace inversion
 * @brief Functions for counting inversions using Merge Sort algorithm
 */
namespace inversion {

// Functions used --->
// int mergeSort(int* arr, int* temp, int left, int right);
// int merge(int* arr, int* temp, int left, int mid, int right);
// int countInversion(int* arr, const int size);
// void show(int* arr, const int size);

/**
 * @brief Function to merge two sub-arrays.
 *
 * @details
 * merge() function is called from mergeSort()
 * to merge the array after it split for sorting
 * by the mergeSort() funtion.
 *
 * In this case the merge fuction will also count and return
 * inversions detected when merging the sub arrays.
 *
 * @param arr    input array, data-menber of vector
 * @param temp   stores the resultant merged array
 * @param left   lower bound of `arr[]` and left-sub-array
 * @param mid    midpoint, upper bound of left sub-array,
 *               `(mid+1)` gives the lower bound of right-sub-array
 * @param right  upper bound of `arr[]` and right-sub-array
 * @returns number of inversions found in merge step
 */
template <typename T>
uint32_t merge(T* arr, T* temp, uint32_t left, uint32_t mid, uint32_t right) {
    uint32_t i = left;       /* i --> index of left sub-array */
    uint32_t j = mid + 1;    /* j --> index for right sub-array */
    uint32_t k = left;       /* k --> index for resultant array temp */
    uint32_t inv_count = 0;  // inversion count

    while ((i <= mid) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count +=
                (mid - i +
                 1);  // tricky; may vary depending on selection of sub-array
        }
    }
    // Add remaining elements from the larger subarray to the end of temp
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // Copy temp[] to arr[]
    for (k = left; k <= right; k++) {
        arr[k] = temp[k];
    }
    return inv_count;
}

/**
 * @brief Implement merge Sort and count inverions while merging
 *
 * @details
 * The mergeSort() function implements Merge Sort, a
 * Divide and conquer algorithm, it divides the input
 * array into two halves and calls itself for each
 * sub-array and then calls the merge() function to
 * merge the two halves.
 *
 * @param arr   - array to be sorted
 * @param temp  - merged resultant array
 * @param left  - lower bound of array
 * @param right - upper bound of array
 * @returns number of inversions in array
 */
template <typename T>
uint32_t mergeSort(T* arr, T* temp, uint32_t left, uint32_t right) {
    uint32_t mid = 0, inv_count = 0;
    if (right > left) {
        // midpoint to split the array
        mid = (right + left) / 2;
        // Add inversions in left and right sub-arrays
        inv_count += mergeSort(arr, temp, left, mid);  // left sub-array
        inv_count += mergeSort(arr, temp, mid + 1, right);

        // inversions in the merge step
        inv_count += merge(arr, temp, left, mid, right);
    }
    return inv_count;
}

/**
 * @brief Function countInversion() returns the number of inversion
 * present in the input array. Inversions are an estimate of
 * how close or far off the array is to being sorted.
 *
 * @details
 * Number of inversions in a sorted array is 0.
 * Number of inversion in an array[1...n] sorted in
 * non-ascending order is n(n-1)/2, since each pair of elements
 * contitute an inversion.
 *
 * @param arr   - array, data member of std::vector<int>, input for counting
 * inversions
 * @param array_size    - number of elementa in the array
 * @returns number of inversions in input array, sorts the array
 */
template <class T>
uint32_t countInversion(T* arr, const uint32_t size) {
    std::vector<T> temp;
    temp.reserve(size);
    temp.assign(size, 0);
    return mergeSort(arr, temp.data(), 0, size - 1);
}

/**
 * @brief UTILITY function to print array.
 * @param arr[]   array to print
 * @param array_size    size of input array arr[]
 * @returns void
 *
 */
template <typename T>
void show(T* arr, const uint32_t array_size) {
    std::cout << "Printing array: \n";
    for (uint32_t i = 0; i < array_size; i++) {
        std::cout << " " << arr[i];
    }
    std::cout << "\n";
}

}  // namespace inversion
}  // namespace sorting

/**
 * @brief Test implementations
 * @returns void
 */
static void test() {
    // Test 1
    std::vector<uint64_t> arr1 = {
        100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84,
        83,  82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67,
        66,  65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50,
        49,  48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33,
        32,  31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
        15,  14, 13, 12, 11, 10, 9,  8,  7,  6,  5,  4,  3,  2,  1};
    uint32_t size1 = arr1.size();
    uint32_t inv_count1 = 4950;
    uint32_t result1 = sorting::inversion::countInversion(arr1.data(), size1);
    assert(inv_count1 == result1);
    // Test 2
    std::vector<int> arr2 = {22, 66, 75, 23, 11, 87, 2, 44, 98, 43};
    uint32_t size2 = arr2.size();
    uint32_t inv_count2 = 20;
    uint32_t result2 = sorting::inversion::countInversion(arr2.data(), size2);
    assert(inv_count2 == result2);
    // Test 3
    std::vector<double> arr3 = {33.1, 45.2, 65.4, 76.5, 1.0,
                                2.9,  5.4,  7.7,  88.9, 12.4};
    uint32_t size3 = arr3.size();
    uint32_t inv_count3 = 21;
    uint32_t result3 = sorting::inversion::countInversion(arr3.data(), size3);
    assert(inv_count3 == result3);
    // Test 4
    std::vector<char> arr4 = {'a', 'b', 'c', 'd', 'e'};
    uint32_t size4 = arr4.size();
    uint32_t inv_count4 = 0;
    uint32_t result4 = sorting::inversion::countInversion(arr4.data(), size4);
    assert(inv_count4 == result4);
}

// /**
//  * @brief Program Body contains all main funtionality
//  * @returns void
//  */
// template <typename T>
// static void body() {
//     // Input your own sequence
//     uint_t size;
//     T input;
//     std::cout << "Enter number of elements:";
//     std::cin >> size;
//
//     std::vector<T> arr;
//     arr.reserve(size);
//
//     std::cout << "Enter elements -->\n";
//     for (uint64_t i=1; i<=size; i++) {
//         std::cout << "Element "<< i <<" :";
//         std::cin >> input;
//         arr.push_back(input);
//     }
//
//     if (size != arr.size()) {
//         size = arr.size();
//     }
//
//     std::cout << "\n";
//     sorting::inversion::show(arr.data(), size);
//     std::cout << "\n";
//
//     // Counting inversions
//     std::cout << "\nThe number of inversions: "<<
//     sorting::inversion::countInversion(arr.data(), size) << "\n";
//
//     // Output sorted array
//     std::cout << "\nSorted array -->  \n";
//     sorting::inversion::show(arr.data(), size);
// }

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // Run test implementations
    // body(); // test your own array
    return 0;
}