# Complexity of Double Selection Sort

I would like to find the best, average, worst-case complexities of below code.

Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position

def double_selection_sort(arr):
n = len(arr)
for i in range(int(n/2)):
_min, _max = i, n-i-1
for j in range(i+1, n-i-1):
if arr[_min] > arr[j]:
_min = j
if arr[_max] < arr[j]:
_max = j
arr[i], arr[_min] = arr[_min], arr[i]
arr[n-i-1], arr[_max] = arr[_max], arr[n-i-1]


I think its in the order of O(nlogn).

The selection sort has this property that number of swaps is at most $$n$$, finding element to its proper place, so it takes $$\mathcal O(n)$$ swaps in the worst case. There is no mechanism to ignore swaps or detect sortedness, two loops are passing through every element, so we can simply infer that best case is equal worst case and equal average case.
Two nested loops with arithmetic progression (array elements to be viewed decrease by one each step) $$\sum_{i=1}^{n-1}i = \frac{1}{2}(n^2-n)$$ are now decreased, giving $$\frac{1}{4}(n^2-n)$$, so still $$\mathcal O(n^2)$$ for all cases.