# Insertion Sort Advanced Analysis

# Insertion Sort Advanced Analysis

christine_e_hill + 4 comments Was anyone else surprised to learn that BIT is not in the editorial? When using Python, merge sort repeatedly timed out for me on this challenge, so I watched a million or so videos and finally used a Binary Index Tree.

The best video is this one.

Purvi_ + 0 comments thanks, really good explanation...

padhy_surya + 0 comments Good One

ShubhamBaghel + 1 comment Can you please explain how to use BIT to solve this problem?

hiigi + 1 comment Number of shifts for arr[i] is equal to the count of elements in arr[0..i-1] whose value is greater than arr[i], which can be calculated with BIT efficiently

huyphatpro + 0 comments How does the BIT calculate the number of elements (in range arr[0 .. i-1]) whose value is greater than arr[i]?

duckhiem95 + 0 comments I'm surprised that BIT tree despite having 10^10 operations in theory passes all test cases. My implementation was only 15 lines. Very nice idea!

andreshp + 3 comments I wanted to thank HackerRank Team for their job. I learnt a lot resolving this problem. I had to wait 4 months to learn c++ pointers to understand binary trees implementations! But it was worth the wait :)

abhiranjan + 1 comment Thanks :)

Your kind words keep us motivated.kbhaskar580 + 0 comments good platform to judge yourself..

*thanks hackerrank team*

kapil2905 + 1 comment Hi I too used Binary tree but my solution timed out for case 7, could you please share your approach. Thanks

vipulvikram + 0 comments You can use binary index tree

dmytro_ovdiienko + 0 comments In case if input array is sorted (or partially sorted), generic binary tree solution will give you O(N^2) instead of O(N log N).

ramkumar_tce_cse + 5 comments Use long for counting the number of shifts.

WickedCube + 0 comments thanks that helped.

Mersaul4 + 0 comments Thanks so much for this!! I switched over from Python and number of shifts was stored in an integer. Code passed most of the test cases except for the last few. Was desperately debugging, but couldn't figure out what was wrong until your comment came to the rescue.

Goto10 + 0 comments Thank you!

lichuan0620 + 0 comments I used unsigned and it appeared to be good enough

ankit_hackerrank + 0 comments how is it possible that just by switching from int to long saves on time?

ross_mcconnell53 + 0 comments Even the Problem Setter's code times out on the tests on submissions for this problem. (It is posted in the Editorial for the problem -- try it!)

It seems to me that tests should determine whether the submitter has come up with an algorithm with the desired O(n log n) bound, while allowing a generous enough constant factor in the running time to allow the submitter to make reasonable implementation decisions. These include choice of language and other implementation choices, discussed at length in the postings, that people had to change in order to get their submissions to avoid timing out. This problem is easy to fix, by checking whether the submission runs in some reasonable multiple of the time taken by the problem tester's code. The problem tester's code, which is in Java, also appears in the editorial section for this problem.

This is a minor suggestion for improving what I regard as a fantastic site.

Thanks, Ross McConnell, Associate Professor of Computer Science, Colorado State University, Ross.McConnell@colostate.edu

jorgefca + 4 comments A little tip for Python 2: after a couple of submissions ending in timeout for the last 3 cases (using merge sort invertion count) I tried to optimize everything and eventually got all correct. A big time saver is using a variable to do the array length comparisons (it got me around 20% performance increase) :

`lvar = len(arr)`

`while i < lvar :`

instead of

`while i< len(arr)`

yusuf_musleh + 0 comments Also keep in mind, that list.append(elem) is faster than list1 += list2, it helped in passing the last 3 cases for me.

AnaghHegde + 0 comments how did u do in python ? for me its giving TLE for last 6 cases

AnaghHegde + 0 comments [deleted]rishabh_ags + 1 comment FYI len(arr) is O(1) https://stackoverflow.com/questions/1115313/cost-of-len-function

tsealex + 0 comments That's right, but function calls will add additional (though small) overhead to the execution because it requires the CPU to allocate a new stack frame and save the registers used by the caller. Their effect on the performance should be unnoticable in most cases (except when you run the program in hackerrank).

alexkogulko + 3 comments For everyone, who have TLE for last 3 cases with

**python BIT**solution - just try to switch for**PyPy3**!d_d_smirnova + 0 comments How on earth does that work?! Great! Thanks)

alejandro_carra1 + 0 comments you are a saviour, I was ready to change implementation completely!

alex_x_yonder + 0 comments You are my hero!

ace_dexter + 2 comments Why do we have to use Merge_sort? I didn't get as the question says the analysis for Insertion sort!

tieros + 0 comments Perhaps they wanted to make us study on another sorting algorithm. Question says "Is there some other way we can calculate the number of shifts an Insertion Sort performs when sorting an array?"

For last 2 days I've been studying binary search tree, and now I'm starting to study merge sort :)

rellehr + 0 comments You don't have to. Use a binary tree. For each item you put in the tree, the number of shifts increments by the number of items in the tree that are greater than it. Much easier to implement than a sort.

Oliver_Queenn + 1 comment Simple C++ using Merge Sort ==>>

#include <iostream> using namespace std; int temp[100000]; long int join(int s[], int left, int mid, int right) { long int shift=0; int i=left, j=mid, k=left; while(i<mid && j<=right) { if(s[i] <= s[j]){ temp[k]=s[i]; k++, i++; } else{ temp[k]=s[j]; k++, j++; shift += mid-i; } } while(i<mid){ temp[k] = s[i]; k++, i++; } while(j<=right){ temp[k] = s[j]; k++, j++; } while(left<=right){ s[left] = temp[left]; left++; } return shift; } long int mergeSort(int s[], int left, int right) { long int shift = 0; if(left < right) { int mid = left + (right-left)/2; shift += mergeSort(s, left, mid); shift += mergeSort(s, mid+1, right); shift += join(s, left, mid+1, right); } return shift; } int main() { int n, t; cin >> t; while(t--) { cin >> n; int s[n]; for(int i=0; i<n; i++) cin >> s[i]; long int shift = mergeSort(s, 0, n-1); cout << shift << endl; } return 0; }

vithaniruchit + 0 comments [deleted]

vishnu_007 + 1 comment Use simple merge sort technique as it is O(nLogn) where as insertion sort is O(n^2)

#include<iostream> #include<cstdio> using namespace std; long long ans=0; void mergei(int arr[],int l,int r,int mid) { int ni=mid-l+1; int nj=r-mid; int L[ni],R[nj]; for(int i=0;i<ni;i++) L[i]=arr[i+l]; for(int j=0;j<nj;j++) R[j]=arr[j+mid+1]; int i=0,j=0,k=l; while(i<ni && j<nj) { if(L[i]<=R[j]) arr[k++]=L[i++]; else { arr[k++]=R[j++]; ans+=(ni-i); } } for(;i<ni;) arr[k++]=L[i++]; for(;j<nj;) arr[k++]=R[j++]; } void m_sort(int a[],int i,int j) { int mid=(i+j)/2; if(i<j) { m_sort(a,i,mid); m_sort(a,mid+1,j); mergei(a,i,j,mid); } } int main() { int t; scanf("%d",&t); while(t--) { int n; ans=0; scanf("%d",&n); int * a = new int[n]; for(int i=0;i<n;i++) scanf("%d",&a[i]); m_sort(a,0,n-1); cout<<ans<<endl; } return 0; }

Good_Imagination + 1 comment I understand how the merge sort work....but my mind can't get the line "shifts += ni - i".....I can't understand this line counts the shifts....if anyone is generous enough to explain it would be appreaciated.

dimonb + 0 comments https://www.geeksforgeeks.org/counting-inversions/ here is good explanation

Wizmann + 3 comments I got TLE with C++ and Accepted with C++14.

I use Binary Indexed Tree which might be the right solution for this problem.

:(

rschwieb + 1 comment My C++ solution that timed out on the last three cases got a perfect score when I switched to C++14. Kind of lame! I did not use a BIT, I just used the basic inversion-counting algorithm.

haved + 0 comments Yup, exactly the same. I'm not sure if it's input handeling or what, but std::ios_base::sync_with_stdio didn't make a difference. Maybe scanf() would work in just "C++"

raunak95 + 0 comments Hey. Same case. Let me know if you ever get to know the reason behind the same.

danglingP0inter + 0 comments I had the same problem. Only switching to C++14 did wonders. Don't know why it happened. Btw, C++14 is slower then C++12

Sort 225 Discussions, By:

Please Login in order to post a comment