You may want to use a struct tm to hold integer values for the month, day, and year that the user enters. But keep in mind that this structure normally has the month from 0-11 and the year is a two-digit value based on the year 1900 (that is, 2004 is represented with the value 104). Using the struct tm properly lets you use other time-manipulation functions.
You could also make your own struct and keep dates "normal", or just use the struct tm with "normal" values. Either way, for the sorting would then recommend qsort (assuming C). What you would need to do is make your own comparison function.
Well, I see I'm already assuming too much about how you are defining records, the language you are using, and other such things. Do you have a start that you can show?