三种排序算法及复杂度

示例：

1. 插入排序：逐个插入已排序前缀。时间 $O(n^2)$，空间 $O(1)$。

2. 归并排序：分治+合并。时间 $O(n\log n)$，空间 $O(n)$。

3. 快速排序：选 pivot 分区递归。平均 $O(n\log n)$，最坏 $O(n^2)$。

---

Original Explanation

1. Insertion sort: place each new item into the correct position in the sorted prefix. $O(n^2)$ time, $O(1)$ space.
2. Merge sort: divide & conquer, merges sublists. $O(n\log n)$ time, $O(n)$ space.
3. Quick sort: pick pivot, partition, recurse. Average $O(n\log n)$, worst $O(n^2)$.