Complexity of Double Selection Sort

Question

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

Thanks in Advance

Answer 1

This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload.
Since the change is minor, you can simply read complexity from basic selection sort.

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.