Optimizing my sorting function

Question

I created my own list sorting function with Python:

def mysort(l):
 for i, (x, y) in enumerate(zip(l, l[1:])):
 if y < x:
 l[i], l[i + 1] = l[i + 1], l[i]
 mysort(l)
 else:
 return l

And:

>>> mysort(l)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> 

I was thinking that how I would be able to optimize this function.

This function is recursive, thus it runs many times + it has a for loop.

Would it be possible to optimize like with O(log(n))?

• Mast: "I was thinking that how I would be able to optimize this function." Just as an exercise, I assume? After all, lists have a builtin sort method.
• Jörg W Mittag: "Would it be possible to optimize like with O(log(n))?" – No, this is impossible. The lower bound for comparison-based sort is O(n log n). In other words: comparison-based sort cannot possibly be faster than O(n log n). I will not give a proof here, but the proof is not rocket science, it is routinely assigned as homework in undergrad CS courses. There are non-comparison based sorts that take advantage of additional information and structure be be faster than O(n log n), but obviously that means the additional information and structure does need to exist. Selection sort is an ...
• Jörg W Mittag: ... example of an algorithm that is faster than O(n log n), it is O(n). However, O(log n) is not possible at all. It should be clear that in order to sort n elements, I have to look at each element, which means sort cannot possibly be better than O(n). The proof for this is a bit more involved, it is based on the fact that whatever order you choose to visit the elements in and whatever method you choose to reorder them, even if there is only one element you don't look at, you can arrange for that element to be of such a value that it will end up in the wrong place.
• U13-Forward: @Mast I know, I am trying to create my own without those functions.

Answer 1

The sorting function that you have implemented is a variant of bubble sort, which has a time complexity of O(n^2) in the worst case. This means that the time taken by the algorithm grows quadratically with the size of the input.

To optimize this function, you can use a more efficient sorting algorithm such as quicksort, which has a time complexity of O(n * log(n)) in the average case and O(n^2) in the worst case. Quicksort works by selecting a pivot element and partitioning the list around it, such that all the elements smaller than the pivot are placed before it and all the elements larger than the pivot are placed after it. This process is then repeated recursively on the left and right partitions until the list is fully sorted.

Here's an example of how you can implement quicksort in Python:

def quicksort(l):
 if len(l) <= 1:
 return l
 pivot = l[0]
 left = [x for x in l[1:] if x < pivot]
 right = [x for x in l[1:] if x >= pivot]
 return quicksort(left) + [pivot] + quicksort(right)

This implementation has a time complexity of O(n * log(n)) in the average case, and it can be optimized further by using techniques such as pivot selection and in-place sorting.

I hope this helps! Let me know if you have any questions.