Timsort：归并排序的工程进化（Python/Java 默认排序）
Timsort 在归并基础上检测自然有序段、短段用插入，最好 O(n)、最坏仍 O(n log n)。
你每天都在用的排序，可能就是归并排序的工程版。Python 的 list.sort / sorted、Java 的 Arrays.sort 都用 Timsort。
图：Timsort = 自然run检测 + 归并 + 短段插入的工程混合
# Timsort 三板斧：
# 1) 扫描自然有序段 run（升序或降序，降序翻转）
# 2) 像归并一样合并 run，并用 galloping 模式加速
# 3) 长度 < 32 的短 run 直接用二分插入排序
# 结果：对“部分有序”的真实数据最好 O(n)，最坏仍 O(n log n)
它本质上是“归并排序 + 自然 run 检测 + 短段插入”的混合，把教科书归并排序打磨成了工业级默认排序。理解归并排序，就掌握了 Timsort 的骨架。
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…