A quick implementation of the thanos sort algorithm, removing half of the array's elements at a time until the array is sorted

thanos_sort.py

from random import randint

def thanos_sort(array):
	while not is_sorted(array):
		target_length = int(len(array)/2)
		while len(array) > target_length:
			del array[randint(0, len(array)-1)]
	return array
	
def is_sorted(array):
	for i in range(len(array)-1):
		if array[i] > array[i+1]:
			return False
	return True

int(len(array)/2) == len(array) // 2

In Russia we usually use "stalin sort", it traverses a list and removes all the elements that break the order...

https://en.m.wikipedia.org/wiki/Longest_increasing_subsequence

This is O(n^2 log n) because deleting an arbitrary element from an array is an O(n) operation.

It can easily be done in O(n log n) by choosing n/2 random elements and copying them all to a new array at once.

This is O(n^2 log n) because deleting an arbitrary element from an array is an O(n) operation.

It can easily be done in O(n log n) by choosing n/2 random elements and copying them all to a new array at once.

I think the original would be O(n^2). Is that what you meant?