We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Insertion Sort Advanced Analysis
  5. Discussions

Insertion Sort Advanced Analysis

  • anarod_val25
     + 0 comments

    Note: Turn the "result" in main into a long long (c++).

    For those doing it in c++, I threw long long at everything I found. Including, the main, where lo and behold, the "result" is an int! So ofcs it was not giving the right result for extra long arrays!!!!!!

    Here's my solution, modified Fenwick tree:

    long long insertionSort(vector<int> arr) {
    long long count = 0, fenSum = 0;
    static vector<int> fenwick(10000001, 0); 
    fill(fenwick.begin(), fenwick.end(), 0);

    for (int n : arr) {
        count += fenSum;
        int idx = n;
        while (idx) {
            count -= fenwick[idx];
            idx -= idx & -idx;
        }

        idx = n;
        while (idx < 10000001) {
            fenwick[idx] += 1;
            idx += idx & -idx;
        }

        fenSum += 1;
    }

    return count;
}