# Does this sorting algorithm already exist? And if so, what is its name?

I created this algorithm off the top of my head this morning. It has one loop, therefore it has a time complexity of O(n) and only stores two variable during loop so it has a space complexity O(1) time. Please correct me if the last statement is wrong. I looked online and I don't see other sorting algorithms that look like mine nor have the complexity I just mentioned. In short, did I just create a new sorting algorithm or does this sorting algorithm already exist? And if it already exists, what is its name (i.e. what type of sorting algo is it)?

def sort_algo(lst):
mid = len(lst) // 2
left = 0
right = len(lst) -1
nextup = left + 1
nextdown = right - 1

while left < right or right > left:
if lst[left] >= lst[mid]:
lst[left], lst[mid] = lst[mid], lst[left]

if lst[left] > 0:
if lst[left] > lst[nextup]:
lst[left], lst[nextup] = lst[nextup], lst[left]

if lst[right] <= lst[mid]:
lst[right], lst[mid] = lst[mid], lst[right]

if lst[right] < lst[nextdown]:
lst[right], lst[nextdown] = lst[nextdown], lst[right]

left += 1
right -= 1

print(lst)

sort_algo([7,2,1,6,8])
sort_algo([2,1,3,4,5])
sort_algo([2,1,3,9,4])
sort_algo([20,1,13,50,4])

• It's not a sorting algorithm because it does not sort. – orlp Dec 18 '18 at 19:18
• Try sorting [2, 1, 3, 4, 5]. – Pontus Dec 18 '18 at 19:19
• @Pontus The algorithm's been adjusted to cope with that one…but now, of course, it breaks on [6, 5, 4, 3, 2, 1]. – Draconis Dec 18 '18 at 21:19

Unfortunately, this has no name—because it doesn't work. Pontus provided a good test case.

lst = [2, 1, 3, 4, 5]
sort_algo(lst)
print(lst)


[2, 1, 3, 4, 5]

It's been mathematically proven that comparison-based sorting algorithms (that is, sorting algorithms based on comparing elements against each other, rather than exploiting certain clever tricks) can never do better than $$O(n \log n)$$ time. Even if you use the clever tricks, you can't do better than $$O(wn)$$ time, where $$w$$ is related to the size of the values. (For radix sort, the classic "exploiting clever tricks" algorithm, $$w$$ is a constant which must be larger than the log of the largest element in the data set.)

EDIT: Your change to the algorithm makes it work on that test case, so here's a new one to break it.

[6, 5, 4, 3, 2, 1] → [3, 2, 1, 5, 4, 6]