Стандартные словари Python неупорядочены (до Python 3.7). Даже если вы отсортируете пары (ключ, значение), вы не сможете сохранить их в dict таким образом, чтобы сохранить порядок.
Самый простой способ - использовать OrderedDict, который запоминает порядок, в котором были вставлены элементы:
In [1]: import collections
In [2]: d = {2:3, 1:89, 4:5, 3:0}
In [3]: od = collections.OrderedDict(sorted(d.items()))
In [4]: od Out[4]: OrderedDict([(1, 89), (2, 3), (3, 0), (4, 5)])
Не обращайте внимания на способ, которым od распечатывается; все будет работать так, как ожидалось:
In [11]: od[1] Out[11]: 89
In [12]: od[3] Out[12]: 0
In [13]: for k, v in od.iteritems(): print k, v ....: 189 23 30 45
Python 3
Для пользователей Python 3 нужно использовать .items() вместо .iteritems():
In [13]: for k, v in od.items(): print(k, v) ....: 189 23 30 45
Ответ 2
Для CPython / PyPy 3.6 и любого Python 3.7 или выше это легко сделать с помощью: