В ходе обсуждения с товарищем docent2007 статьи о сортировке «Милосердный Сталин» у нас сами собой родились дополнительные, весьма полезные методы сортировки. Эти методы определённо могут пригодиться каждому.
Либеральная сортировка
Либеральная сортировка уважает каждое значение и его "право" на место.
def liberal_sort(arr):
# Каждый элемент остается на своём месте, потому что все равны
return arr
То есть массив возвращается таким, какой он есть, без изменений, поскольку "у каждого элемента своё уникальное место, которое нельзя нарушить".
Есть еще вариант Либеральной сортировки, где все элементы группируются по какому-то общему признаку, чтобы "никто не чувствовал себя изолированным". Внутри каждой группы порядок сохраняется.
from collections import defaultdict
def liberal_sort_with_groups(arr, key_func=lambda x: x):
# Группируем элементы по ключу, но внутри групп порядок сохраняется
groups = defaultdict(list)
for item in arr:
groups[key_func(item)].append(item)
result = []
for group in groups.values():
result.extend(group)
return result
arr = [5, 3, 8, 3, 1, 8, 5]
sorted_arr = liberal_sort_with_groups(arr, key_func=lambda x: x % 2)
print(sorted_arr)
# нечетные и затем четные, но порядок в группах сохранен
# -> [5, 3, 3, 1, 5, 8, 8]
