MinFinder Implementation in Python
Last year, I had to analyze the MinFinder sorting algorithm for my university course. As the corresponding paper (MinFinder: A New Approach in Sorting Algorithm) only provided Pseudocode and I couldn’t find a prior implementation, I decided to program it myself in Python.
You can get a copy of the source code in my GitHub Repository.
You can see my notes regarding the time and space complexity below.
Input orders for worst, average and best case
- Worst Case: Reverse sorted array
- Average Case: Random array
- Best Case: Sorted array
Space complexity: In-place algorithm → O(1)
Comparisons: (n−1) + (n−2) + ⋯ + 1 = (n * (n-1)) / 2
- Worst Case: See amount of comparisons
- Average Case: Half of worst case
- Best Case: 0
- Worst Case: n * (n-1)
- Average Case: 3/4 * n * (n-1)
- Best Case: (n * (n-1)) / 2
Conclusion: MinFinder has a time complexity of O(n²) for every input.