// A program to sort an array of numbers by Charles Nye
// best with a dense set of numbers, with few gaps between.

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

//helper function taken from Olaf's program:
void printArray(int *arr, int N)
{
  for ( int i=0; i<N; ++i ) cout << " " << arr[i];
  cout << endl;
}

//helper to generate consecutive random numbers
vector<int> getinputvector( const int length){

  //initialize rand with a seed
  srand ( time (NULL));
  vector<int> input;
  input.reserve ( length );
  for (int i=0; i<length; i++) input.push_back(i); //fill vector with consecutive numbers
  random_shuffle (input.begin(), input.end() );
}


  const bool verbose = true;

int main()
{
  // how many numbers to sort
  int length = 10;
  cin >> length;

  vector<int> input = getinputvector(length);

  if ( verbose )
    {
        cout << "Input: ";
        printArray(input, length);
    }

//find the min and max values in the array by pulling ever bigger and smaller ones out.
    int maxval = input[0];
    int minval = input[0];

    for (int i=0; i<length; i++)
    {
        if (input[i] > maxval)
        maxval = input[i];
        if (input[i] < minval)
        minval = input[i];
    }

if ( verbose )
    {
        cout << "Max/Min are: " << maxval << " " << minval << endl;
    }
//assert: maxval and minval are the largest and smallest numbers in start[]


//set up the expanded array to sort into. "()" will initialize it to "0".
    int range = (maxval-minval+1);
    int * expanded = new int[(range)]();
if ( verbose )
    {
        cout << "Range is: " << range << endl;
    }
//fill the expanded array.
    for (int i=0; i<length; i++)
        expanded[ ( input[i]-minval ) ] = input[i];
    ;
//assert: the array is sorted, but has extra zeros in it.


//copy the expanded array into compacted array, sans zeros, for output.
    int compacted[length];
    for (int i=0,j=0 ; i<(range) ; i++ )
        {
            if (expanded[i] != 0)
                compacted[j++] = expanded[i];
        }
    ;
//assert: compacted is the sorted list.


//print to show work, always print the result.
 if ( verbose )
    {
        cout << "Expanded to: " << endl;
        printArray(expanded, range);
        cout << "Sorted to: " << endl;
    }
printArray(compacted, length);

//clean-up the dynamic memory.
delete[] expanded;

    return 0;
}