Envío 3620

Código

import random


def exchange(array, i, j):
    array[i], array[j] = array[j], array[i]


def sort(array, lo, hi):
    if hi <= lo:
        return

    less_than_idx = lo
    greater_than_idx = hi
    current_idx = lo + 1

    pivot = array[lo]
    while current_idx <= greater_than_idx:
        current = array[current_idx]
        if current < pivot:
            exchange(array, less_than_idx, current_idx)
            less_than_idx += 1
            current_idx += 1
        elif current > pivot:
            exchange(array, current_idx, greater_than_idx)
            greater_than_idx -= 1
        else:
            current_idx += 1

    sort(array, lo, less_than_idx - 1)
    sort(array, greater_than_idx + 1, hi)


n = int(input())
array = [int(x) for x in input().split()]
random.shuffle(array)  # To avoid worst case scenario
sort(array, 0, n - 1)
print(*array)