This is not that simple, the sort is done at database level and the app only get small parts of the data, it never have the 800 000 songs in memory or anywhere to group it would require another very slow query. So the app have no idea of the index of the first item for a given letter.
And as a reminder the app support [Wiki] Smart filters so infinite complexity on the queries so the worst case is very far from linear.
Everything is relatively simple at little scale on a computer, but at large scale on a low end mobile device this is a completely different story.