Support pad/backfill/nearest reindexing even for unsorted indexes by storing a sorted index?
Recently, I've been working on adding a 'nearest' method to reindexing: https://github.com/pydata/pandas/pull/9258

It occurs to me that we could easily extend reindexing/get_indexer methods to work with unordered indexes if we were willing to do a sort operation on the index if necessary. This would probably entail saving the sorted result on the parent index, similarly to how get_indexer is currently supported on MultiIndex by creating a tuple index internally.

I think this would be a nice usability gain over the current implementation, and not be _too_ surprising. Sorting indexes (once) is pretty fast, for anything up to millions of rows.

Thoughts?
