After digging a little bit in `Contacts`' DB here is what I found. 

As already said by @grgarside, the DB is in 

    ~/Library/Application\ Support/Address\ Book/Sources/<source-ID>/AddressBook-v22.abcddb

Where `<source-ID>` is most likely the most recent modified directory. 

`AddressBook-v22.abcddb` is a SQLite DB file with 24 tables (in my case). The most important one is `ZABCDRECORD` which holds (among others) the firstname, lastname and the creation date of the contact (but also modification etc). <br /><br />


The 2 interesting columns in your case are : 

* ZCREATIONDATE
* ZMODIFICATIONDATE

As [I found out recently][1], the base date for these 2 columns is 01-01-2001. 
The columns `ZMODIFICATIONDATEYEARLESS` and `ZCREATIONDATEYEARLESS`  use the 1st January of creation year as the base date. 

Using `sqlite` you can sort it like that : 

`sqlite3 AddressBook-v22.abcddb "select ZFirstName, ZLastName from ZABCDRECORD order by ZMODIFICATIONDATE"`

It will output FirstName/LastName sorted by modification date. 



  [1]: http://apple.stackexchange.com/questions/114168/dates-format-in-messages-chat-db