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


  • 2
    $\begingroup$ It's not a sorting algorithm because it does not sort. $\endgroup$ – orlp Dec 18 '18 at 19:18
  • 2
    $\begingroup$ Try sorting [2, 1, 3, 4, 5]. $\endgroup$ – Pontus Dec 18 '18 at 19:19
  • $\begingroup$ @Pontus The algorithm's been adjusted to cope with that one…but now, of course, it breaks on [6, 5, 4, 3, 2, 1]. $\endgroup$ – 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]

[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]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.