How to determine the complexity of the sorting algorithm?

Question

How to determine the complexity of the sorting algorithm?

There is a sorting algorithm:

def search(a):
    if len(a) < 2:
        return a
    pivot = a[0]
    left = [int(i) for i in a[1:] if i < pivot]
    right = [int(i) for i in a[1:] if i > pivot]
    
    return search(left) + [pivot] + search(right)

I want to determine its complexity, can you tell me how to do it?

2

алгоритм python сортировка сложность

Author: Kromster, 2020-07-28

Source

1 answers

score 7 · Accepted Answer

In my opinion, this is a fast sorting algorithm, the complexity is in the average case O(nlogn), in the worst case O(n^2)

In the worst case, the smallest or largest element is selected as the reference element, and then the array will be divided each time into an array of length 1 and n-1
In the average case, the array is divided logn times (that is, approximately in half) and at each division, all elements are checked more or less than they are the reference

Also I advise you to choose a random element as a reference element or an average one for the case of a partially sorted array