#![allow(non_snake_case)]
#![allow(unused_variables)]
use std::fs;
use std::fs::File;
use std::io::{BufWriter, BufReader};
use std::io::prelude::*;
use std::str;

fn insertion_sort(v: &mut[u32]) {
    if v.len() < 2 {
        return;
    }
    for i in 1..v.len() {
        let mut j = i;
        while j > 0 && v[j - 1] > v[j] {
            v.swap(j, j-1);
            j -= 1;
        }
    }
}
fn partition(pivot: u32, v: &mut[u32]) -> usize {
    let mut lft = 0;
    let mut rgt = v.len() - 1;
    loop {
            while lft < v.len() && v[lft] < pivot {
                lft +=1;
            }
            while v[rgt] > pivot && rgt > 0 {
                rgt -=1;
            }
            if lft >= rgt {
                return rgt;
            }
            v.swap(lft, rgt);
            lft += 1;
            rgt -= 1;
    };
}

fn sort_vec(v: &mut[u32]) {
    if v.len() < 64 {
        insertion_sort(v);
        return;
    }
    let pivot = v[v.len() / 2];
    let mid = partition(pivot, v);
    sort_vec(&mut v[0..=mid]);
    sort_vec(&mut v[mid+1..]);
}

fn main() {
    let mut buffer: Vec<u8> = Vec::with_capacity(32);
    let mut infile = BufReader::new(fs::File::open("algsort.in").expect("File empty!"));
    infile.read_until(b'\n', &mut buffer).expect("Could not read N");
    let N = str::from_utf8(&buffer).expect("Unable to parse N").to_owned();
    let N = N.trim().parse::<u32>().unwrap();
    let mut V: Vec<u32> = Vec::with_capacity(N as usize);
    for _ in 0..N {
        buffer.clear();
        infile.read_until(b' ', &mut buffer).expect("Could not read item");
        let x = str::from_utf8(&buffer).expect("Unable to parse N").to_owned();
        let x = x.trim().parse::<u32>().unwrap();
        V.push(x);
    }
    // V.sort();
    sort_vec(&mut V);
    let mut writer = BufWriter::new(File::create("algsort.out").unwrap());
    V.iter().for_each(|x| {
        write!(writer,"{x} ").unwrap();
    });
}