Introduction

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.

Analysis

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

Space complexity: In-place algorithm → O(1)

Time complexity

Comparisons: (n−1) + (n−2) + ⋯ + 1 = (n * (n-1)) / 2

Accesses:

• Worst Case: See amount of comparisons
• Average Case: Half of worst case
• Best Case: 0

Total:

• 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.