The problem with the loss of focus when adding something to the playlist is still present. It was already on the list but it isn't anymore and hasn't been fixed.
The problem is not in the display, but inserting or adding it to a hash...
The sorting doesn't even take that long, it's getting it into a sortable object, array, hash, or DB takes a long time when dealing with 2.1 million records...
On a much lesser processor, (an ARM7) I was able to get sub-second access to 100k ID3 records, and the response time stayed linear up to my bounds test of 1 million records. ...and I was doing this in 24k ("k", not "m") of RAM.
The record count doesn't mean anything, that's the purpose of a hash. Short of the file system having issues with fseek() you should be able to hit any place in that index file almost instantly. Once you're there, it's a short hop to your data.
Build the hash, save it to an indexed file, and you should be good. There's no reason to re-load the hash every time. In fact, since the data is static, you should be able to ship it pre-built with the release.
I'm happy to give you more specific help.... just PM me an example of the data (even just 20 random records) and I can generate a couple of million more from that. I'll carve out some code and get it back to you.
When I jump from Navigation to Media for example, the mute button toggles and sound mutes. I had this already on the 4.1. This occures almost every time I jump to the media screen from somewhere else. I have an external USB soundcard if that matters.