Number of swaps to sort when only adjacent swapping allowed.
Am not able to understand the logic.
Problem link
https://www.geeksforgeeks.org/number-swaps-sort-adjacent-swapping-allowed/
There is a HackerRank problem on this topic.
Ref: Merge Sort: Counting Inversions | HackerRank
The underlying principle is that you have to sort the array with minimum adjacent swaps, and that’s what Merge Sort does.
Merge Sort essentially breaks the array into two halves continuously and swaps the adjacent elements to sort it every sub-array, and merges all the pieces aftferwards. So, using a user-defined Merge Sort function in which we count the number of swaps done by the algorithm, we can essentially solve this problem in O(n logn) time complexity.
1 Like
Thankyou… 
1 Like