As the question was updated to ask for the difference between
sort is deprecated) and
sort_index, the answer of @mathdan is no longer reflecting the current state with the latest pandas version (>= 0.17.0).
sort_valuesis meant to sort by columns
sort_indexis meant to sort by the index (or a specific level of the index)
sort (deprecated starting from pandas 0.17.0) and
sort_index where indeed almost identical (both methods could sort by both columns and index). But this confusing situation has been solved in 0.17.0.
For an overview of the changes in the sorting API, see http://pandas.pydata.org/pandas-docs/stable/whatsnew.html#changes-to-sorting-api