calculating the number of “inversions” in a permutation

by

You can use the merge sort algorithm.

In the merge algorithm’s loop, the left and right halves are both sorted ascendingly, and we want to merge them into a single sorted array. Note that all the elements in the right side have higher indexes than those in the left side.

Assume array[leftIndex] > array[rightIndex]. This means that all elements in the left part following the element with index leftIndex are also larger than the current one in the right side (because the left side is sorted ascendingly). So the current element in the right side generates numberOfElementsInTheLeftSide – leftIndex + 1 inversions, so add this to your global inversion count.

Once the algorithm finishes executing you have your answer, and merge sort is O(n log n) in the worst case.

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. How to sort in-place using the merge sort algorithm?
  3. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  4. Finding three elements in an array whose sum is closest to a given number
  5. Given an array of numbers, return array of products of all other numbers (no division)
  6. Algorithm to find k smallest numbers in array of n items
  7. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  8. Can min/max of moving window achieve in O(N)?
  9. Weighted random selection from array
  10. Print two-dimensional array in spiral order
  11. How to find a duplicate element in an array of shuffled consecutive integers?
  12. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  13. Given an array, find out the next smaller element for each element
  14. Binary Search algorithm implementations
  15. Algorithm to determine if array contains n…n+m?
  16. Find the 2nd largest element in an array with minimum number of comparisons
  17. Algorithm to rotate an array in linear time
  18. Maximum single-sell profit
  19. In-place array reordering?
  20. How to find max. and min. in array using minimum comparisons?
  21. Median of 5 sorted arrays
  22. find pair of numbers in array that add to given sum
  23. Finding out the duplicate element in an array
  24. Regarding in-place merge in an array
  25. Interview question: three arrays and O(N*N)
  26. How to find repeating sequence of characters in a given array?
  27. Maximum sum of non consecutive elements
  28. Finding kth smallest number from n sorted arrays
  29. Algorithm to apply permutation in constant memory space
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment