Implemented Stooge sort in Python3 (Bubble sort & Quicksort)

[There seems to be a sort called Stooge sort. ](Https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%82%A5%E3%83%BC%E3%82%B8%E3%82%BD % E3% 83% BC% E3% 83% 88) This sort algorithm seems to be a very __inefficient __sort algorithm, which is less efficient than bubble sort.

In this article, I'll implement Stoogesort in Python3.

#Sort the list destructively. The algorithm is "Stooge sort"
def stooge_sort(ls):
    stack = [(0, len(ls) - 1)]
    
    while stack:
        i, j = stack.pop()
        if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]
        
        if j - i + 1 >= 3:
            t = (j - i + 1) // 3
            stack.extend(((i, j - t), (i + t, j), (i, j - t)))

if __name__ == '__main__':
    import random

    ls = list(range(30))
    random.shuffle(ls)

    print(ls)
    stooge_sort(ls)
    print(ls)

# [20, 4, 13, 28, 12, 0, 17, 19, 22, 21, 5, 23, 3, 27, 14, 2, 29, 11, 24, 7, 15, 9, 25, 6, 26, 18, 8, 1, 10, 16]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

It seems that you can sort properly. The idea (?) Is that it is implemented repeatedly instead of recursion ... Is it meaningful to implement it efficiently for inefficient algorithms? (´ ・ ω ・ `)

Next is efficiency. [Inefficient "bubble sort"](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82 % BD% E3% 83% BC% E3% 83% 88) and Efficient "Quicksort" I would like to implement% E3% 83% 83% E3% 82% AF% E3% 82% BD% E3% 83% BC% E3% 83% 88) and measure the time to sort a list with 1000 elements. I think.

#Sort the list destructively. The algorithm is "Stooge sort"
def stooge_sort(ls):
    stack = [(0, len(ls) - 1)]
    
    while stack:
        i, j = stack.pop()
        if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]
        
        if j - i + 1 >= 3:
            t = (j - i + 1) // 3
            stack.extend(((i, j - t), (i + t, j), (i, j - t)))


#Sort the list destructively. The algorithm is "bubble sort"
def bubble_sort(ls):
    t = len(ls)

    for i in range(t - 1):
        for j in range(i + 1, t):
            if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]


#Sort the list destructively. The algorithm is "quicksort"
def quick_sort(ls):
    stack = [(0, len(ls) - 1)]

    while stack:
        left, right = stack.pop()
        if left >= right: continue

        pivot = ls[left + (right - left) // 2]
        i, j = left, right
        while True:
            while ls[i] < pivot: i += 1
            while ls[j] > pivot: j -= 1

            if i >= j: break
            
            ls[i], ls[j] = ls[j], ls[i]
            i, j = i + 1, j - 1

        stack.extend(((j + 1, right), (left, i - 1)))

if __name__ == '__main__':
    import random, copy, time

    ls = list(range(1000))
    random.shuffle(ls)
    
    bubble_ls = copy.deepcopy(ls)
    bubble_start = time.time()
    bubble_sort(bubble_ls)
    bubble_time = time.time() - bubble_start

    quick_ls = copy.deepcopy(ls)
    quick_start = time.time()
    quick_sort(quick_ls)
    quick_time = time.time() - quick_start

    stooge_ls = copy.deepcopy(ls)
    stooge_start = time.time()
    stooge_sort(stooge_ls)
    stooge_time = time.time() - stooge_start

    print("bubble : {}".format(bubble_time))
    print("quick  : {}".format(quick_time))
    print("stooge : {}".format(stooge_time))

    # bubble : 0.0938718318939209
    # quick  : 0.0
    # stooge : 33.47836709022522

Slow ((((´ ・ ω ・ `))))