# MinFinder Implementation in Python

2021-07-12

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