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.