UVa 10327

From Algorithmist
Jump to: navigation, search

10327 - Flip Sort[edit]


This is the standard problem of counting the number of inversions in a string of length n\leq 1000. N length is medium; you can choose the brute-force O(n^{2}) algorithm, where you will barely get accepted, or use more optimized algorithms.


One of the possible solutions is using merge sort to count the number of inversions, which will lead to a nice O(n\log(n)) algorithm. While merging two sorted arrays, any move from the right array to the final merged array will represent a number of inversions if the left array is not empty. If, for example, the left array has 3 elements left, then the merge have fixed 3 inversions in one step.

The final inversion count is the sum of all inversions fixed by all the merges done by the algorithm.


  • The problem does not state the width of the integers. Better be safe and stick to long long.



1 2 3
2 3 1


Minimum exchange operations : 0
Minimum exchange operations : 2


Introduction to Algorithms, Chapter 2 - Getting Started, Question 2-4, 'Inversions'