Count Inversions in an array | Set 1 (Using Merge Sort) | GeeksforGeeks

Explanation for the article: www.geeksforgeeks.org/counting...
This video is contributed by Harshit Jain.

[@AnhTu-en9gk]

This is awesome. I come here from an algorithm course from Stanford. Your explanation is clearer.

[@ceciliaw1065]

Amazing amazing explanation with examples, thank you so much

[@maximilianoromayfigueroa1815]

thanks for the awesome video, I learned a lot and in a very short period of time ;)

[@GeeksforGeeksVideos]

Correction at 05:58 --> "the index of element 3 is smaller than the index of element 2." Correction at 10:53 --> "Time Complexity for Simple Method is O(n^2)." [It can also be written as O(n*n)]

[@MrSrikanthpai]

Nice explanation. Liked it.

[@deniz.7200]

Thanks for the video, should we also count the inversion happened before merge started??

[@goutamkundu6392]

in the video 08.50 it is "we add the inversion count returned by these two respective calls to inversion count variable". But I am seeing only in the last call inv_count += _mergeSort(arr,temp,mid+1,right) is there

[@GeeksforGeeksVideos]

Thanks for pointing it out, Goutam. You're right, it's a typo. There should be a plus sign there. The statement should look like this: inv_count += _mergeSort(arr, temp, left, mid);

[@alieser7770]

you are the best!!!

[@ariabanazadeh1016]

just amazing

[@kautukraj]

Very helpful!

[@MisterAadj]

geek4geeks u guys awesome

[@lovleshbhatt7797]

Please increase the volume level, its quite less for hearing & understanding

[@dsadaddy8403]

its fine increase yours.

[@lalithsamanthapuri932]

Thanks a Lot Sir..

[@GeeksforGeeksVideos]

You're welcome!

[@subham-raj]

Why did you take "temp" array?

[@pranavsingh9284]

Merge karenge to extra , to merged to temp le lete apan kyu ki inplace merging nhi kr sakte

[@tanishqupadhayay1350]

why do we add mid-i to inv_count??

[@davemustainejigsaw]

hi, the method 1 described in the code , shouldn't the condition be if((arr[i] > arr[j])&&(i

[@GeeksforGeeksVideos]

No, since the inner loop runs from j=i+1 so the (i

[@abhishek_sengupta]

Thanks a lot!!!

[@danielhazel7205]

does this work for duplicate numbers in an array?

[@adithyabhat4770]

Thank you so much for the video!

[@MadhuKumari-gy7uz]

Cleared my concept, thanks brother

[@sanjananl2501]

I am unable to dry run the following two lines of code inv_count += _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); in _mergesort. Pls help

[@dsadaddy8403]

share the full code then only we can answer

[@kurdi_x5842]

thamk you helped me alot

[@anujg3366]

I came after seeing today gfg potd question :)

[@tingzhao3931]

nice vid

[@_-ghost-_711]

If I want to print the elements in inversion, then what will be the time complexity.....

[@Santosh-om7qk]

n^2

[@subham-raj]

It will be nlogn

[@subham-raj]

@@Santosh-om7qk You need to improve your skills

[@AdeshPaul]

Samjhane ke liye dhanyavaad. kya aap yeh bta sakte hain ki agar merge sort aur enhanced merge sort ki same time complexities hain to dono me se konsi behtar hai? Agrim Dhanyavaad.

[@shubhamlahoti9758]

enhanced one is just for the purpose of counting inversions in array

[@vineetkothari2839]

nice

[@soumelee5661]

4:14 how to get number of inversions ✔✔✅✅ 4:58 examples

[@67_ujjwalsolanki78]

number of likes represent the number of times I fell asleep watching this

[@delyartabatabai9636]

This is CLRS problem 2-4

[@karthikshetty3851]

It doesnt clear all test Cases

[@rupakdas7161]

Worst explanation I have ever seen of an algorithm and just reading the lines of code no dry run how can a beginer understand without doing a dry run

[@youtube_username_]

It bothers me that he starts talking about mid as if we're supposed to know what mid is.

[@FaizaanDatoo]

For a more thorough description, I recommend consulting Kleinberg and Tardos: Algorithm Design (the PDF is one of the first results on Google). The relevant text is Chapter 5 - Divide and Conquer, and the section is 5.3 - Counting Inversions. This video helped me understand that section, but I wouldn't have been able to figure it out without both the text and the video.

[@DSA_Coding]

boring

[@shreyaskulkarni9994]

Why is he whispering? So annoying