// T06-16.cpp : ���� ���� �������� ������� "main". ����� ���������� � ������������� ���������� ���������.
//

#include <iostream>
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct LIST
{
    int VALUE;
    int INDEX;
    struct LIST* NEXT;
    struct LIST* PREVIOUS;
};

void swap(int* a, int* b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

void SWAP(struct LIST* a, struct LIST* b)
{
    swap(&a->VALUE, &b->VALUE);
}

struct LIST* ADD(struct LIST* current_list, int value)
{
    struct LIST* temp = (struct LIST*)malloc(sizeof(struct LIST));
    struct LIST* temp_next = current_list->NEXT;
    current_list->NEXT = temp;
    temp->VALUE = value;
    temp->NEXT = temp_next;
    temp->PREVIOUS = current_list;
    if (temp_next != NULL)
    {
        temp_next->PREVIOUS = temp;
    }
    return (temp);
}

struct LIST* DELETE(struct LIST* current_list)
{
    struct LIST* previous = current_list->PREVIOUS;
    struct LIST* next = current_list->NEXT;
    if (previous != NULL)
    {
        previous->NEXT = current_list->NEXT;
    }
    if (next != NULL)
    {
        next->PREVIOUS = current_list->PREVIOUS;
    }
    free(current_list);
    return previous;
}

struct LIST* partition(struct LIST* LEFT, struct LIST* RIGHT)
{
    struct LIST* PIVOT = LEFT;
    int pivot_counter = fmin(2, RIGHT->INDEX - LEFT->INDEX - 1);
    //int pivot_counter = rand() % (RIGHT->INDEX - LEFT->INDEX);
    for (int i = 0; i < pivot_counter; i++)
    {
        PIVOT = PIVOT->NEXT;
    }
    cout << "CHOOSE = " << PIVOT->INDEX << " : " <<  PIVOT->VALUE << endl;
    while (LEFT->INDEX <= RIGHT->INDEX)
    {
        while (LEFT->VALUE < PIVOT->VALUE)
        {
            LEFT = LEFT->NEXT;
        }
        while (RIGHT->VALUE > PIVOT->VALUE)
        {
            RIGHT = RIGHT->PREVIOUS;
        }
        if (LEFT->INDEX >= RIGHT->INDEX)
        {
            break;
        }
        SWAP(LEFT, RIGHT);
        LEFT = LEFT->NEXT;
        RIGHT = RIGHT->PREVIOUS;
    }
    return RIGHT;
}

void quickSort(struct LIST* LEFT, struct LIST* RIGHT)
{
    if (LEFT->INDEX < RIGHT->INDEX)
    {
        struct LIST* BOUND = partition(LEFT, RIGHT);
        cout << "starting SORT FROM = " << LEFT->INDEX << " : " << LEFT->VALUE << " to " << BOUND->INDEX << " : " << BOUND->VALUE << endl;
        quickSort(LEFT, BOUND);
        cout << "!ended! SORT FROM = " << LEFT->INDEX << " : " << LEFT->VALUE << " to " << BOUND->INDEX << " : " << BOUND->VALUE << endl;
        LIST* temp = LEFT;
        while (temp->PREVIOUS != NULL)
        {
            temp = temp->PREVIOUS;
        }
        while (temp != NULL)
        {
            cout << temp->VALUE << "\t";
            temp = temp->NEXT;
        }
        cout << endl;
        cout << endl;
        cout << "starting SORT FROM = " << BOUND->NEXT->INDEX << " : " << BOUND->NEXT->VALUE << " to " << RIGHT->INDEX << " : " << RIGHT->VALUE << endl;
        quickSort(BOUND->NEXT, RIGHT);
        temp = LEFT;
        while (temp->PREVIOUS != NULL)
        {
            temp = temp->PREVIOUS;
        }
        while (temp != NULL)
        {
            cout << temp->VALUE << "\t";
            temp = temp->NEXT;
        }
        cout << endl;
        cout << "!ended! SORT FROM = " << BOUND->NEXT->INDEX << " : " << BOUND->NEXT->VALUE << " to " << RIGHT->INDEX << " : " << RIGHT->VALUE << endl;
        cout << endl;
        cout << endl;
    }
}

int main(void)
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    struct LIST* l = (struct LIST*)malloc(sizeof(struct LIST));
    struct LIST* p = l;
    l->VALUE = 0;
    l->NEXT = NULL;
    l->PREVIOUS = NULL;
    int temp;
    int size = 0;
    while (scanf("%d", &temp))
    {
        size++;
        l->INDEX = size;
        l->VALUE = temp;
        l = ADD(l, 0);
    }
    size--;
    l = DELETE(l);
    quickSort(p, l);
    //SWAP(p, p->NEXT->NEXT);
    while (p != NULL)
    {
        printf("%d ", p->VALUE);
        //cout << p->VALUE << "\t";
        p = p->NEXT;
    }
    //cout << endl;
    return 0;
}

/* 1 9 2 8 3 7 4 5 ^D */

/* 2 8 3 7 4 5 ^D */

/* 8 7 4 5 ^D */