Recall that an inversion in a sequence of numbers a1, a2, · · · , an is defined as a pair of indices i and j such that i < j and ai > aj . As an extension of this definition, we define a significant inversion to be a pair of indices i and j such that i < j and ai > 2aj .

(a) Design and write a O(nlogn) divide and conquer algorithm that will, given a sequence of n numbers, output the number of significant inversions in the sequence. 

(b) Implement your algorithm in Java. Your implementation takes a sequence numbers as input, and outputs the number of significant inversions and all significant inversions.

Answer rating: 100% (QA)

Divide and Conquer Algorithm for Significant Inversions Divide Divide the sequence into two halv... View the full answer