Envío 3625

Código

import random

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


def insertion_sort(array, lo, hi):
    for i in range(lo, hi + 1):
        j = i
        while j > 0 and array[j] < array[j-1]:
            array[j], array[j - 1] = array[j - 1], array[j]
            j -= 1


def hoare_partition(array, lo, hi):
    i = lo
    j = hi + 1
    pivot = array[lo]

    while True:
        i += 1
        while array[i] < pivot:
            i += 1
            if i == hi:
                break

        j -= 1
        while array[j] > pivot:
            j -= 1
            if j == lo:
                break

        if i >= j:
            break

        exchange(array, j, i)

    exchange(array, lo, j)
    return j


def sort(array, lo, hi):
    if hi <= lo:
        return
    if hi - lo <= 10:
        insertion_sort(array, lo, hi)
    else:
        j = hoare_partition(array, lo, hi)
        sort(array, lo, j - 1)
        sort(array, j + 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)