خب بریم ببینیم چرا اون لیست اولیه که sort نشده بود سریع تر بود:

ما یه لیست داریم که توش ۱ میلیون اعداد رندوم که بین هزار تا ۱۰ میلیون قرار داره، وجود داره.
وقتی این اعداد دارن داخل مموری ساخته میشن آدرس هایی از مموری که پشت هم هستن، بهشون تعلق میگیره، مثلا: (سمت چپ آدرس های مموری - سمت راست خود اعداد)
100....131 —> 34225
100....132 —> 775325
100....133 —> 1031
...
وقتی ما لیست رو به اون روش sort میکنیم چه اتفاقی میفته ؟ "رفرنس" ها جاشون عوض میشه. آبجکت های جدید ساخته نمیشه. تستش بکنیم:
lst = ['b', 'a', 'c']
for i in lst:
print(i, id(i))
print("------------------------------")
for i in sorted(lst):
print(i, id(i))
این تا اینجا.

حالا ما چیو تست گرفتیم؟ iteration روی این دو لیست رو.
وقتی cpu داره از ابتدا شروع میکنه به گرفتن آیتم ها، توی لیست اولیه با آدرس های متوالی از مموری طرف هست. یعنی آیتم اولی رو که گرفت، آیتم دومی بغل گوشش هست میگیره... ولی توی لیست دوم وقتی آیتم اول رو گرفت، آیتم بعدی ممکنه هزار تا خونه اونور تر باشه توی مموری.

حالا دقیقا چی میشه که کند میشه؟
جواب: Cache misses.

(این یه مثال کاملا ساده شده بدون پیچیدگی های موجود هست)
ریل های قطار رو در نظر بگیرید که از یه جایی به بعد دو شاخه میشن و هر شاخه یه مسیر جدا رو میره. فرض کنید شما مسئول این هستید که قطار رو به مسیر درستش هدایت کنید.
همچنین فرض کنید از قبل به شما برنامه ای ندادن که فلان قطار باید چه مسیری بره. حالا چیکار میکنید ؟

دو تا راه دارید: یا هر قطاری که اومد نگهش دارید و ازش بپرسید کدوم سمت میره تا وصلش کنید بهش... یا اینکه چپ و راست رفتنش رو حدس بزنید....
قطار ها باری هستن و بسیار سنگین... هزینه ی سنگینی باید بدیم تا قطار هارو وایسونیم و هزینه ی سنگینی باید بدیم تا دوباره شروع به حرکت کنن.

میایم گزینه دوم رو انتخاب میکنیم... اگه درست گفتیم که خیلی عالی اگه غلط گفتیم چی؟ مسیر و اشتباه میره بعد قطار وایمیسته مجبوره برگرده اون مسیر رو و مسیر درست رو بره...

این اتفاقی هست که داره توی cpu میفته و با نام Branch Prediction میشناسنش. امروزه cpu ها با توجه به الگوریتم هایی که دارن بیشتر از این که اشتباه پیشبینی کنن ، درست پیشبینی میکنن پس خیلی میتونن optimize تر عمل کنن ولی خب همچنان cache miss وجود داره مخصوصا توی الگوی رندوم و این میشه که کند تر میشه.