12.9. Implementation of Merge Procedure with Counting

Try these first

1. 1.

   Define an inversion in the context of rankings.

   Hint

   Think about pairs of items in terms of order.

2. 2.

   What is the time complexity of counting inversions using the brute-force method?

   Hint

   Consider the number of comparisons you need for each item.

3. 3.

   What is the time complexity of counting inversions using merge sort?

   • O(n^2)
   • O(n log n)
   • O(n)

   Hint

   Think about how merging elements affects overall performance.

4. 4.

   True or False: Every pair of rankings with no inversions are identical.

   • True
   • False

   Hint

   Reflect on the definition of inversion.

5. 5.

   Design an algorithm that counts inversions in O(n log n) time and identify its key components.

   Hint

   Focus on how merging sorted lists relates to counting inversions.

6. 6.

   Given two users' ranking lists, A = [3, 1, 2, 5, 4] and B = [2, 1, 3, 5, 4], find the number of inversions between them.

   Hint

   Consider how to map one ranking into the order of another.