How would you sort a huge array of ages?

How would you sort a huge array of ages?

Consider you have a huge array of numbers that represent the ages of the employees in a company and you want to write an efficient algorithm to sort this array. How would you do and what is the Big O of this algorithm?

Answer: if you were sorting a regular array, you could just use the merge sort and have a great O(n . lg n) , but... Wait a minute... Can we have an even more efficient solution? Sure! This is a very specific set of data, that represents the employees ages. Since we know about the data scope, we can use this knowledge to get to an O(n) algorithm. Let's see how!

Developing the Solution:
  In the known real world ages can vary between 0 and 122, but let's make our solution effective up to the next few decades or more and assume the maximum value should be 150. Since we know that the huge array is a distribution of integer values within this range, we could easily

1. Count in O(n) how many employees have each age between 0 and 150, with a single loop, storing the values in a temporary array (each index is an age and each value is the count)
2. Overwrite in O(n) the input array values using the counts of each age,  since an array always has its indexes ordered!

Show me the code!
For the sake of time I've written the code in JavaScript. Feel free to write it in Java or you favorite language

//Global var

MAX_AGE = 150;

//Main

function sortAges(a /* unsorted array */){ if(! isValid(a)) return a; var c= countAges(a); /* temp array of age counts*/ for(var i=0, j=0; i< c.length; i++){ var count=c[i]; if(!count) continue ; for(var k=0; k<count; k++){ a[j+k]=i; } j=j+k; } return a /*sorted array of ages*/; }

//Helper

function countAges(a /*array of ages*/){ var c= new Array(MAX_AGE + 1); for(var i=0; i < c.length; i++){ c[i]=0; } for(var i=0; i< a.length; i++){ c[a[i]]++; } return c; }

//Validation

function isValid(a /* anything!*/){ if( typeof(a)!="array" && typeof(a)!="object") return false; if(!a.length) return false; try{ for(var i=0; i<a.length; i++){ var v=a[i]; if(typeof(v)!= "number") return false; //it doesn't handle decimals if(v < 0 || v > MAX_AGE) return false; } } catch(e){ return false; } return true; }

//Code to generate data for algorithm validation

function createRandomAgesArray(n /*new array length*/){ var a=[]; for(var i=0; i<n; i++){ a[i]= getRamdomAge(); } return a; }

function getRamdomAge(){ return Math.round( MAX_AGE * Math.random() ); }

//Generating data and testing

MAX_AGE=18; //making it simple to verify

var a= createRandomAgesArray(10); 

console.log(a);

sortAges(a);

console.log(a);

MAX_AGE=150; //change beck to maximum value