# UVa 10327

## Contents

## 10327 - Flip Sort[edit]

## Summary[edit]

This is the standard problem of counting the number of inversions in a string of length . N length is medium; you can choose the brute-force algorithm, where you will barely get accepted, or use more optimized algorithms.

## Explanation[edit]

One of the possible solutions is using merge sort to count the number of inversions, which will lead to a nice 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.

## Gotchas[edit]

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

## Notes[edit]

- You may also like to check UVa 10810

## Input[edit]

3 1 2 3 3 2 3 1

## Output[edit]

Minimum exchange operations : 0 Minimum exchange operations : 2

## References[edit]

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