Short Problem Definition:
Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of times Insertion Sort shifts each elements when sorting an array?
If ki is the number of elements over which the ith element of the array has to shift, then the total number of shifts will be k1 +k2 +…+kN.
time complexity is O(N*log(N))
space complexity is O(1)
There are more solutions with nlogn time for this challenge. I decided to use Binary Indexed Trees as they are a data structure I am not that familiar with. The other solution includes a modified merge-sort that is posted as the problem editorial. BITs are effective for computing cumulative frequencies in log(N) time and are therefore perfectly suited for this problem. They assume a full tree and therefore are bound to the maximal range defined in the problem specification.
#!/usr/bin/py class BinaryIndexedTree(): def __init__(self, sz): self.sz = sz self.tree =  * sz def update(self, idx, val): while (idx <= self.sz): self.tree[idx] += val idx += (idx & -idx) def read(self, idx): sum = 0 while (idx > 0): sum += self.tree[idx] idx -= (idx & -idx) return sum if __name__ == '__main__': t = input() for _ in range(t): n = input() arr = map(int, raw_input().split()) cnt = 0 bit = BinaryIndexedTree(10**7+1) for val in reversed(arr): bit.update(val, 1) cnt += bit.read(val-1) print cnt
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.