Retrieve list of songs ordered by last play time in iOS

I need to obtain a list of the N most recently played songs from an iOS device, in order.

The only way I can imagine doing it, at the moment, is by getting all the songs through an MPMediaQuery and manually sort them by lastPlayedDate.

This is a potentially expensive operation and I was wondering if there was a better approach.

---

Edit: After some tests, this is a very expensive operation. On a test library of 2500 songs, it took around 20 seconds to:

1. Get all the songs.
2. Assign a date to all songs that had never played (January 1 1970).
3. Order them by date.
4. Fetch the first N entries.

Any suggestion of improvements would be appreciated.

---

Edit 2: Solved now, but just for the record here's what I was doing.

I was sorting using a block as described here: https://stackoverflow.com/a/805589/112702. Simply changing the sorting method to what's in Bryan's answer improved my speed by nearly 20 times on an iPod Touch 3.

One way is to take the array of MPMediaItems you get from the MPMediaQuery and sort it by MPMediaItemPropertyLastPlayedDate using an NSSortDescriptor:

NSTimeInterval start  = [[NSDate date] timeIntervalSince1970];

MPMediaQuery *songsQuery = [MPMediaQuery songsQuery];
NSArray *songsArray = [songsQuery items];

NSSortDescriptor *sorter = [NSSortDescriptor sortDescriptorWithKey:MPMediaItemPropertyLastPlayedDate
                                                         ascending:NO];
NSArray *sortedSongsArray = [songsArray sortedArrayUsingDescriptors:@[sorter]];

NSTimeInterval finish = [[NSDate date] timeIntervalSince1970];
NSLog(@"Execution took %f seconds.", finish - start);

This sorts the new array by most recently played first. I tested this on a iPhone 4S using 2000 songs and it took .98 seconds.