摘要
该实验基于已归档的单机微基准，在CPython 3.12.14与Windows11环境下，对100、1000、5000个整数在random与nearly_sorted两类输入上比较内置sorted()与自实现插入排序的整函数调用耗时中位数。计时包含插入排序函数内列表复制成本，每条件重复7次并与sorted结果校验。结果显示内置sorted()各条件耗时中位数均低于插入排序，且插入排序在nearly_sorted下低于其random对应值；结论限于该归档条件的描述性观察。
关键词：Python排序；插入排序；微基准；耗时中位数；实验报告
第一章 实验目的与问题界定：单机微基准下两种排序实现的规模与数据分布响应
本实验围绕一个可回答的中心问题展开：在CPython 3.12.14与Windows11（10.0.22621）的单机环境下，对100、1000、5000个取值于0至999999的整数，Python内置sorted()与自实现插入排序在random与nearly_sorted两类输入上的整函数调用耗时中位数，如何随数据规模与分布变化。该问题限定于已归档的微基准记录，不涉及对两种排序算法作一般性优劣定论，也不试图回答何种算法在普遍意义上更优。
实验目的定为描述性比较：在同一机器、同一解释器版本、同一计时口径下，呈现两种实现在六个条件组合中的耗时中位数差异，并观察插入排序在两类输入上的响应差别。所谓整函数调用耗时，指time.perf_counter覆盖从函数调用开始到返回的整段过程；自实现插入排序在函数内复制列表，故复制成本计入耗时。因此，本实验不能表述为已排除输入复制或纯算法层面的公平比较，两类实现的读数差异同时包含实现方式与调用组织方式的贡献。
据此，本实验不据此推断现实业务性能、其他机器或其他数据分布下的表现，也不作因果机制归因。全文按原理与实现差异、实验条件与数据生成、实验步骤与中位数对照、误差来源与结论边界的顺序展开：先说明两种实现的算法原理与可观察差异，再交代归档环境、随机种子与输入构造，随后呈现六条件中位数并作同口径解读，最后讨论计时口径、复制成本与外推限制，以下各章依次说明。
第二章 排序原理与实现差异：内置归并调度与直接插入的双层循环
在上一章明确描述性微基准定位的基础上，本章转向两类实现的算法原理与可观察差异，为后续解释六条件耗时中位数提供依据。内置sorted()由可迭代对象新建有序列表，而list.sort()原地修改列表，在不需保留原列表时后者略高效；这一区别决定了本实验调用sorted()时输入列表本身不被改动。CPython 3.12的归并调度包含Powersort，故不能将旧Timsort的归并栈规则误写为本版本实现，本文只按“内置归并调度”作笼统表述。
插入排序则把记录逐个插入已排序序列：外层遍历除首元素外的所有元素，内层在有序表中自后向前查找并移动，平均与最坏时间复杂度为O(n²)、最好为O(n)，额外辅助空间为O(1)，且为稳定排序[1]。排序作为将任意序列重排为按关键字有序序列的重要操作，其不同插入实现的过程与性能已有专门讨论[1]；内排序算法在程序设计中常被用于解决实际问题，对常见内排序的基本思想与执行过程的剖析有助于理解实现差异[2]。一个排序算法的优劣可以用空间复杂度与时间复杂度来衡量[3]，这为比较两类实现提供了基本维度；但需注意，本实验记录的是整函数调用耗时，而非直接测量比较次数或移动次数，因此上述复杂度分析只能用于形成预期，不能替代实测读数。据此可提出可检验预期：nearly_sorted输入下插入排序内层移动减少，其与random条件的耗时差距应缩小。
需注意区分算法原地辅助空间O(1)与本脚本函数复制列表所需O(n)空间：前者是插入排序的算法性质，后者是计时口径内的实现成本，二者不可混同。这一区分也意味着，后文对两类实现耗时差异的解读，只能限定在归档脚本所定义的整函数调用口径内，不能将其等同于纯算法层面的比较。
第三章 实验条件与数据生成：归档环境、随机种子与两类输入构造
承接上一章对两类实现原理与计时口径的区分，本章说明后续六条件对照所依据的数据来源与生成条件。需要强调的是，本章分析的是已公开归档的单机微基准实验，而非本次新执行的实测；因此下文所列环境、种子与规模均取自归档记录，不构成对其它机器、其它Python版本或其它数据分布的推断基础。
归档环境为CPython 3.12.14与Windows11（10.0.22621），随机种子固定为20261102。输入规模设为100、1000、5000个整数，取值区间为0至999999，并分为random与nearly_sorted两类。其中nearly_sorted类先对序列排序，再随机交换max(1,n//100)次，以构造局部有序但并非完全有序的输入；这一构造方式使该分布在原理上对应插入排序内层移动减少的情形，但其实际影响仍需由后续耗时读数检验，不能预先断言。按六种条件（三种规模×两类分布）各重复7次计，共得到84条记录，全部结果均与内置sorted()的输出校验一致，这为后续中位数对照提供了可比对的正确性前提。
在计时口径上，归档脚本使用time.perf_counter覆盖整个函数调用过程。自实现插入排序在函数内部先对输入列表执行copy，故该复制成本被计入耗时。由此，本章及后续章节呈现的读数是归档脚本所定义的整函数调用耗时，既不能表述为已排除输入复制，也不能等同于纯算法层面的公平比较；这一限定与上一章关于算法原地辅助空间O(1)同脚本复制列表O(n)的区分保持一致。本文使用的归档实验脚本与84条原始计时记录可直接核查。它们仅用于单机微基准的描述性分析，不外推至其他环境或现实业务场景。
第四章 实验步骤与中位数对照：六条件耗时结果的呈现与解读
承接上一章所界定的归档条件与计时口径，本章按归档脚本的实际流程说明六条件耗时结果的取得与呈现方式。脚本先以固定随机种子20261102生成两类输入，再对每个规模与分布的每种组合分别调用内置sorted()与自实现插入排序；每次调用均由time.perf_counter覆盖整个函数执行区间，插入排序函数内部的列表复制成本因此计入读数。每条件重复7次，六条件合计84条记录，各次输出均与sorted()结果校验一致，随后按条件汇总中位数。需要说明的是，上述步骤是对归档脚本流程的复述，而非本次重新执行的实测；因此下文读数只代表该归档记录，不构成对其它运行情形的测量。
六条件的中位数对照如下表所示，单位为秒，数值保留至归档记录所示精度。
| 分布 | 规模 | sorted() | 插入排序 |
|---|---|---|---|
| random | 100 | 0.0000030 | 0.0001638 |
| random | 1000 | 0.0000738 | 0.0211067 |
| random | 5000 | 0.0004669 | 0.5544802 |
| nearly_sorted | 100 | 0.0000015 | 0.0000117 |
| nearly_sorted | 1000 | 0.0000118 | 0.0006731 |
| nearly_sorted | 5000 | 0.0000870 | 0.0145966 |
从同口径同环境的描述性差异看，内置sorted()在全部六个条件下的耗时中位数均低于自实现插入排序。就插入排序自身而言，nearly_sorted分布在三个规模上的中位数均低于其random对应值：规模100时由0.0001638秒降至0.0000117秒，规模1000时由0.0211067秒降至0.0006731秒，规模5000时由0.5544802秒降至0.0145966秒。这一方向与上一章所述局部有序输入减少内层移动的原理预期一致，但此处仅作现象描述，不作因果归因。
还需指出，上述对照仅反映该归档脚本在单一机器、单一CPython版本与三个规模点上的整函数调用耗时。三个规模点不足以拟合时间复杂度，读数差异也不能直接归因于算法本身，因为计时口径同时包含解释器调用开销与插入排序内部的列表复制成本。因此，本章结果既不构成对复杂度的拟合，也不支持向其他环境或现实业务的推广，其解读范围限于该归档条件下的描述性比较，后续章节将围绕这一边界讨论误差来源与结论限度。
第五章 误差来源与结论边界：计时口径、复制成本与外推限制
前文的中位数对照已表明，在该归档条件下内置sorted()在各条件的整函数调用耗时中位数低于自实现插入排序；但这一读数能否被合理解释，仍取决于计时口径与重复设计所带来的误差边界。首先，time.perf_counter覆盖的是整个函数调用区间，既包含解释器层面的调用开销，也包含自实现插入排序在函数内部复制列表的成本，因此两项实现并非纯算法层面的同口径比较，不能据此宣称某一算法本身更优，也不能表述为已排除输入复制或实现了纯算法公平比较。其次，每条件仅重复7次且只报告中位数，归档材料未提供离散度统计，故本文不编造误差值、置信区间或统计图，也不对中位数之外的数据波动作推断；中位数的稳健性仅在该归档记录范围内成立。
再次，实验限于单一机器、单一CPython 3.12.14版本与100、1000、5000三个规模点，既不能外推到其他硬件、其他数据分布或现实业务场景，也不能由三个规模点拟合时间复杂度，更不能将耗时差异作因果归因。三个规模点只能呈现该归档条件下的描述性差异，不足以支撑关于增长规律的判断。综合全文，本实验支持的是一项描述性观察：在该归档条件下，内置sorted()在各条件的整函数调用耗时中位数均低于自实现插入排序，且插入排序在nearly_sorted各规模上的中位数均低于其random对应值；这一观察不构成对算法优劣的定论。后续可改进的测量设计包括：增加重复次数并报告离散度、将列表复制移出计时区间以分离算法成本与复制成本、扩展规模点与数据分布，并在多环境下复测以检验结论的稳健性。