@mtknn Though it looks like stooge sort is O(n^(log 3 / log 1.5)) which is O(n^2.71...) so I guess yours is "better"/worse

@mtknn

(I have no idea how quickly this runs and it fails if there are duplicates on either side of the halfway point)

@chao
this is almost mergesort, I think, but without the merge step: split the array in half, sort each half, and then combine them together again

at a glance, I'd say it's O(n^2 log n), because the operation [x for x in a if not x in a1] is n^2, and there are log n levels

@kiilas
@chao

I have combined ideas from both of your sorts:

def rsort(a):
if len(a) <= 1:
return a
left = a[:len(a)//2]
right = a[len(a)//2:]
if max(left) > min(right):
random.shuffle(a)
return rsort(a)
else:
return rsort(left) + rsort(right)

the idea is mergesort, but instead of zipper merging, just check if every element in the left sub-array is less than in the right, and if not shuffle