Cacher is the code snippet organizer for pro developers

# # Uses python3
import sys
import random

def partition3(a, left, right):
    pivot = a[left]
    last_lower_element = left
    first_greater_element = right
    current_number = left
    while current_number <= first_greater_element:
        if a[current_number] < pivot:
            a[current_number], a[last_lower_element] = a[last_lower_element], a[current_number]
            last_lower_element += 1
            current_number += 1
        elif a[current_number] > pivot:
            a[current_number], a[first_greater_element] = a[first_greater_element], a[current_number]
            first_greater_element -= 1
            #if current number > pivot, we move this number to the end, shift the rightmost wall one number closer, and 
            # also stay in the current position to evaluate the current number if it continues to be bigger, shift them outward.
            # we only move on if we find a number that is smaller or equal to the current pivot.
        else:
            current_number += 1
            #if current number == pivot, we just move on to the next number
    return last_lower_element, first_greater_element

# 2 way partition will exhibit o(n2) behaviour if there are a lot of equal elements.
def partition2(a, l, r):
    x = a[l]
    j = l;
    for i in range(l + 1, r + 1):
        if a[i] <= x:
            j += 1
            a[i], a[j] = a[j], a[i]
    a[l], a[j] = a[j], a[l]
    return j


def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
   # partition 2 potion
   #  m = partition2(a, l, r)
   #  randomized_quick_sort(a, l, m - 1);
   #  randomized_quick_sort(a, m + 1, r);
    # partition 3 portion
    m1, m2 = partition3(a, l, r)
    randomized_quick_sort(a, l, m1 - 1);
    randomized_quick_sort(a, m2 + 1, r);


# portion for submission
if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))

# test_cases for python tutor
# n = 5
# a = [2, 3, 9, 2, 9]
# n = 6
# a = [6, 5, 4, 3, 3, 3]
# n = 5
# a = [2, 3, 9, 2, 2]
# the below test case fails when there is a random pivot
# n = 8
# a = [2, 4, 3, 4, 7, 8, 9, 9]

randomized_quick_sort(a, 0, n - 1)
for x in a:
    print(x, end=' ')