Python
Python copied to clipboard
Added Count Inversions algorithm (Merge Sort based)
Describe your change:
- [x] Add an algorithm
This pull request adds a Python implementation of the Count Inversions algorithm using a modified Merge Sort approach.
Count Inversions is used to determine how far an array is from being sorted by counting the number of out-of-order pairs (i, j) such that i < j and arr[i] > arr[j]. This has applications in ranking systems, bioinformatics, and measuring list similarity.
Checklist:
- [x] I have read CONTRIBUTING.md.
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, I am not combining unrelated changes.
- [x] All new Python files are placed inside an existing directory.
- [x] All filenames are in all lowercase characters with no spaces or dashes. (Note: The filename is
Count_Inversion.py; I can rename it tocount_inversion.pyif needed.) - [x] All functions and variable names follow Python naming conventions.
- [x] All function parameters and return values are annotated with Python type hints.
- [x] All functions have doctests that pass the automated testing.
- [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.
Wikipedia link: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)