CareerCup

use bit vector to store each integer in single bit. 625 integers are required to store 20000 numbers

int arr[625] = {0};

ex: to store data 2000
arr index = 2000/32 = 62
bit position = 2000%32 = 16

now make bit position 16 of array index 62 arr[62] to 1

using this bit vectors we can store data range from 1 - 20000 in 625 integers..

after storing all data in bit vectors, check all bit positions of arr[0], arr[1]..... arr[625]... if any bit position is set to 1 then store back that data into array

lets arr[10] bit position 15 is set to 1 then this is equivalent to data 10*32+15 = 335

#include <stdio.h>

int main()
{
	int arr[] = {97,75,209,435,430,531,990};
	int vec[625] = {0};
	
	int i;
	int j;
	int n = 1;
	int index = 0, bit_pos = 0;
	for (i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		index = arr[i] / 32;
		bit_pos = arr[i] % 32;
		
		n = n << bit_pos ;
		vec[index] = vec[index] | n;
		n = 1;
	}
	index = 0;
	for (i = 0; i < sizeof(vec)/sizeof(vec[0]); i++)
	{
		for (j = 0; j < 32; j++)
		{
			if ( vec[i] & ( 1 << j ))
			{
				arr[index++] = i*32 + j;
			}
		}
	}
	
	for (i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
		printf ("%d\n", arr[i]);
	return 0;
}

If you can use C++ bitset, just use it

#include <bitset>
using namespace std;

void SpecialSort(int a[], int n = 16000)
{
    bitset<20000> bs;
    const int isize = sizeof(int) * 8; // 32;

    // Iterate all elements in the array
    for (int i = 0; i < n; ++i)
    {
        bs[a[i]] = 1;
    }

    // Iterate [1, 20000]
    for (int i = 1, k = 0; i < 20000; ++i)
    {
        if (bs[i])
            a[k++] = i;
    }
}

Here is C# version

using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            Program exe = new Program();
            exe.SortWithLimit();
        }

        private void SortWithLimit()
        {
            const int intSize = 32;
            const int intLimit = 20000;

            int[] arr = GetRandomArray(25, 1000);

            if (arr.Length > intLimit)
            {
                return;
            }

            Console.WriteLine("Unsorted {0}", string.Join(",", arr));
            
            uint[] vec = new uint[intLimit / intSize];

            int i;
            int j;
            int index = 0;

            for (i = 0; i < arr.Length; i++)
            {
                index = arr[i] / intSize;
     
                vec[index] = vec[index] | (uint) 1 << arr[i] % intSize;
            }

            index = 0;

            for (i = 0; i < vec.Length; i++)
            {
                for (j = 0; j < intSize; j++)
                {
                    if ((vec[i] & (1 << j)) > 0)
                    {
                        arr[index++] = i * intSize + j;
                    }
                }
            }

            Console.WriteLine("Sorted   {0}\n", string.Join(",", arr));
        }

        private int[] GetRandomArray(int intCount, int intMax)
        {
            Random r = new Random();
            List<int> result = new List<int>();

            while (result.Count < intCount)
            {
                int number = r.Next(intMax);

                if (!result.Contains(number))
                {
                    result.Add(number);
                }
            }

            return result.ToArray();
        }
    }
}

We can use external quicksort. In an external quicksort, instead of heaving a single pivot element used for partitioning the array, we have a group of elements called 'middle group' or 'pivot group'. In a generalized algorithm, we use a Doubly Ended Priority Queue, (DEPQ).

1.	Read in "maximum possible" elements and insert them into a DEPQ. The elements in the DEPQ will eventually be the middle group of elements.
2.	Read in the remaining elements.
	•	If the next element is ≤ the smallest element in the DEPQ,
		output this next element as part of the left group.
	•	If the next element is ≥ the largest element in the DEPQ,
		output this next element as part of the right group.
	•	Otherwise, remove either the max or min element from the
		DEPQ (the choice may be made randomly or alternately);
		if the max element is removed, output it as part of the right
		group; otherwise, output the removed element as part of the
		left group; insert the newly input element into the DEPQ.
3.	Output the elements in the DEPQ, in sorted order, as the middle group.
4.	Sort the left and right groups recursively.

However, the question mentions that the range of integers is pretty much same as the number of elements and also the integers are unique.

Thus we can use 'counting sort' instead of a 'Doubly Ended Priority Queue' to sort the middle group elements.

vector<int> sortUnique(vector<int>&num)
{
        int  n = num.size();
         bitset<20000> bs;
         for (int i=0; i < n; i++) bs[num[i]] = 1;
         for (int i=0, k =0; i < 20000; i++)
                         if (bs[i] == 1) num[k++] = i;
         return num;
}