深入解析排序算法之——归并排序

2744557306

1 基础介绍
$ o: E  z: g" ^$ y排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

6 K/ E0 k* G6 D# X' _以下是一些常见的排序算法：
0 ^0 ?' _% r, ~1 }, h  @8 k
4 G8 V0 X/ q& n" {$ z+ W  e冒泡排序（Bubble Sort）
4 _; E9 E$ y! z
插入排序（Insertion Sort）

选择排序（Selection Sort）
4 f3 m* d' }( P$ x' r4 q5 t7 k
- H0 W/ @& A; ^; v% I归并排序（Merge Sort）
4 S! o- W" T* N+ r# @% ^, Q
快速排序（Quick Sort）

& F. [; o( W. ?1 o9 a堆排序（Heap Sort）
: i' E$ |% u- Q! @* _" X
5 I: s4 \! d0 |2 P一、基本介绍介绍
1 G( V4 m6 e% L$ p8 y+ |' c2 p1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
5 I( C+ h  B% i$ i$ s/ }
5 d# E" D* d7 @6 K: d1 e: ?归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
+ t; P: u+ \4 K  M
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

5 P3 r7 I! M  |+ w( g合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

- U$ Z' Z3 M. G" y$ W合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

% f* y. v% B" {+ v4 P比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

1 d  j+ [3 K- m! u' W; c. G+ w8 N重复步骤 2，直到其中一个数组的元素全部放入 C 中。
6 z1 m6 J2 B3 e
! K; ?  y) d% S4 T% ]  ]将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
, F. D- r$ J3 i( b
( \% h- _$ s3 k" `& E- Z8 w原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
# m1 `* {3 i& q( B. A* v! |: {6 q
% ^$ @" @; Z! L3 \; U, i: }) L首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
7 A! {5 G# s9 Y/ \; m
+ M  B' {& }! o$ F1 ^对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

* |; z3 L3 |: h6 t* d对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
+ t4 _+ V7 @; L6 X; z
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 i 指向其起始位置，即 0；对于右半部分，指针 j 指向其起始位置，即 0。比较左右两部分的元素大小，发现左半部分的第一个元素 5 大于右半部分的第一个元素 1，因此将 1 添加到新的数组 sorted_arr 中，并将右半部分的指针 j 向后移动一位。此时，sorted_arr 的内容为 [1]。接着比较左半部分的第二个元素 2 和右半部分的第一个元素 3，发现左半部分的元素较小，因此将 2 添加到 sorted_arr 中，并将左半部分的指针 i 向后移动一位。此时，sorted_arr 的内容为 [1, 2]。接着继续比较左右两部分的元素大小，将它们依次添加到 sorted_arr 中。最终得到排好序的数组 [1, 2, 3, 5, 6]。

! C$ g, n9 A3 A7 J8 B, X因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
7 S( s1 G8 \; Q
+ d* o5 W  p# k7 b1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
3 Y0 l! K" o+ o2 ?" Y
# i' f" Y- ~# F! ]( R这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
1 ]# w- r. v7 r$ v1 H( ^/ L
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
- E. C8 s$ R* A3 H; S1 t" D
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
; B3 u8 K- m5 ?6 P3 H
, d) [$ V) f# E9 c+ D这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

$ |0 Q1 B7 W* u: i/ `: I8 Z3 o1.3使用场景
3 c6 N0 U6 e5 e- w/ L归并排序的应用场景比较广泛，主要适用于以下几种情况：

; |3 ?7 n# n: D8 A对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
7 y/ [& m! n4 @: x1 \  N
1 l9 R  b- D, N- q9 Y) E对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
2 Q5 q, N, i2 J5 E. u
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
! Y" ]( x7 t: w0 w2 e
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
0 r  @, @( ~1 u7 ]
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
/ Q+ g! d" c' E
& Z  R* S' s5 u! s2 z. @& A$ B总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
5 D+ f+ f6 [" a8 `6 g0 J1 f- v* H- \7 r
二、代码实现
1 W8 E9 I6 N1 V/ ]0 N. T+ |2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):5 @9 w: A7 _  X! S4 q1 n- v
   
2.     if len(arr) <= 1:4 h* s\" m1 Y0 e& |8 V/ c
   
3.         return arr
   , Y8 L. D* _+ g9 z3 G$ y
4. - [2 n6 x/ x, j7 X
   
5.     # 将数组分成两个部分# }* Y; ?0 c; `& m1 t8 \7 G! n
   
6.     mid = len(arr) // 2  K4 |\" h+ S9 N) H
   
7.     left_half = arr[:mid]8 E\" o( C& j* l) M  E! \\" ?% R
   
8.     right_half = arr[mid:]
   % ?7 Z4 W, B7 V5 d3 l9 B  w\" |6 t
9. 
   7 w) t; \: w8 S: k
10.     # 对左右两部分分别递归调用归并排序* H7 p* N. ^6 G% V
    
11.     left_half = merge_sort(left_half)
    0 l9 M4 S: O3 ]6 `
12.     right_half = merge_sort(right_half)
    & j( u7 J4 W$ o4 S( B' y5 G
13. 
    7 {8 w' K: s7 F% e
14.     # 合并左右两部分
    , f: I- Z/ c9 i- X* o\" f+ c/ B9 m4 |
15.     return merge(left_half, right_half)
    + m. i\" R: E) a! Q' b+ u5 m9 o
16. & \* B* C) J- ~
    
17. def merge(left_half, right_half):
    8 T! T0 C% Z, Y9 V- M
18.     i = j = 0. E# X6 P4 I( g: c: d
    
19.     merged = []9 L4 ]; W: B1 Y
    
20. 
    7 }$ |( T5 H) U7 u  u. C# [) `
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    8 `0 p5 x8 B: \* b. \( K
22.     while i < len(left_half) and j < len(right_half):$ w0 T& o& a2 v- P/ |\" R
    
23.         if left_half[i] < right_half[j]:7 B) O* m+ L# n  m* i! d% S
    
24.             merged.append(left_half[i])) `; S1 D7 v9 s6 f! ?
    
25.             i += 1; y3 _  p+ e1 Z) ]+ f/ n
    
26.         else:9 Y$ b+ _7 I- e9 k$ l
    
27.             merged.append(right_half[j])
    & A0 b: O. @/ Y2 Y4 Y9 T
28.             j += 1% A; v0 d) D: |8 Y3 R5 T* a+ f
    
29. 
    & d9 ~0 z\" {, _7 G2 _8 F
30.     # 将左右两部分中剩余的元素添加到 merged 中& f6 K9 ?( Q# y\" E8 i6 Q
    
31.     merged += left_half[i:]5 `, Z* ~6 Y# \# J
    
32.     merged += right_half[j:]# {0 c' P8 j# J) y7 A! ]
    
33. 
    & a( ?8 J# X/ K
34.     return merged

复制代码

代码讲解

这个实现使用了两个函数，一个是 merge_sort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。下面对这两个函数进行详细讲解：

merge_sort() 函数

1. def merge_sort(arr):& Q3 c8 T/ _  u* m( V0 r
   
2.     if len(arr) <= 1:
   3 i( f: |8 r3 j2 J5 l. i1 F9 p
3.         return arr: Q; V; T9 C, K' H& F
   
4. 
   ! p& y\" Z6 _2 l4 I! y
5.     # 将数组分成两个部分
   ' A; p9 l+ u/ Q3 b; p
6.     mid = len(arr) // 2
   ) }- |( E/ K( _  n
7.     left_half = arr[:mid]( s/ @5 D+ Z* f* S8 X! T
   
8.     right_half = arr[mid:]. D( K' H& b0 [* C$ d
   
9. 9 a+ B7 O4 d' g4 u' v+ p4 S& |
   
10.     # 对左右两部分分别递归调用归并排序
    . B7 L2 x; E$ B1 E
11.     left_half = merge_sort(left_half)
    2 {\" G8 j% x! ^+ l. u- ]! u
12.     right_half = merge_sort(right_half), q/ _5 \- J& u8 x5 J
    
13. 
    8 O/ k' q' U% H\" _! Q
14.     # 合并左右两部分' R* C3 c: m' J! ?# x5 q
    
15.     return merge(left_half, right_half)' r6 K, y+ u# m1 @+ M1 s* \
    
16. ```
    * R. Z! ?! F. A$ Z
17. 1 e: B8 R% }( V- h( @& z+ n4 p\" p6 m/ i
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    / g. e5 k- I, W) m' _

复制代码

merge() 函数

1. def merge(left_half, right_half):
   + J. j: |/ a9 W8 k6 r
2.     i = j = 0\" R, C+ C' t3 R. D1 Q  H# H
   
3.     merged = []2 z! V# c7 ]4 t* M  U2 Y
   
4. 
   \" t, m\" U$ `, M. L( \# R; t
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   1 ]' c% X& H% V. t) M. f. h
6.     while i < len(left_half) and j < len(right_half):
   $ X3 B; _1 F\" G( C3 Z
7.         if left_half[i] < right_half[j]:& ]5 ^! G& I/ _& G. A: a\" d
   
8.             merged.append(left_half[i])
   . Y5 A. g- _1 z% {: ?
9.             i += 1
   # i$ K% B$ w/ |$ }7 E2 Q
10.         else:0 a: Y4 V1 x& h7 [& X
    
11.             merged.append(right_half[j])
    + k% ~0 ~1 m' _0 `
12.             j += 15 I1 o1 [, f5 R2 X7 C) I
    
13. 
      ]. W# v7 L1 t2 f
14.     # 将左右两部分中剩余的元素添加到 merged 中
    & e2 r9 t\" O- Z0 H
15.     merged += left_half[i:]
    9 c8 w. g. b+ m' z
16.     merged += right_half[j:]! [2 L) L  ~; U5 v+ y5 o5 l4 w
    
17. 
    2 ?; j# U. {$ A8 E+ u0 j
18.     return merged
    \" k1 H( Z$ S5 X- _( h9 k9 n
19. ```8 M( y\" E, }8 M! L
    
20. 
    ! \0 r- _2 r) o! a: Q
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
, p% Z5 c( |3 N- @% k
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
5 h1 Z' x2 ?+ @- |# s; X
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

: T$ s, w* n1 c4 z对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
8 u  F9 `! L$ P! y; C
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

测试
5 ^% _6 S- D2 t! t在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]: l0 A% D, ?7 y4 `- P; w) |
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。

# F8 T. Z# H) L/ q: T0 ?1 `总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

以下是使用 Java 实现归并排序的代码：

1. public class MergeSort {
   ! ^% O3 W( M$ O, @+ y. H, H
2.     public static void main(String[] args) {, t3 v3 X+ U/ F) Y' ~
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};1 z) [5 ]7 |5 a! s7 f7 `2 S6 r
   
4.         mergeSort(arr, 0, arr.length - 1);& [9 J; f. t# @0 m+ Q* N\" i
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   ; N\" Z; G! B# W# o$ C
6.     }
   : L0 _5 O# w6 M8 }8 h8 F
7. 
   * a# T; h: E0 q6 G. u
8.     public static void mergeSort(int[] arr, int left, int right) {
   \" \) S9 C0 _, f4 a. V5 w2 G9 N% `& x
9.         if (left >= right) {2 r9 Z# I# e0 E
   
10.             return;; q9 L, `. b; f( D9 S
    
11.         }
    # C3 o* B4 `( x9 }% P
12. 
    0 I7 M* a8 T& z6 e1 e\" e
13.         int mid = (left + right) / 2;
    + q4 i4 T8 M) \2 Q
14.         mergeSort(arr, left, mid);* G7 u7 x6 `! U) N6 |  _
    
15.         mergeSort(arr, mid + 1, right);! {; S$ v- B, D( _; l! P
    
16.         merge(arr, left, mid, right);
    0 `  d# Q2 t1 S0 ~: I# ~# Y
17.     }
    5 r/ x# M' @7 g& v! a
18. ( u. s+ W) d+ C4 D/ y2 D
    
19.     public static void merge(int[] arr, int left, int mid, int right) {+ S9 r' }# Q8 `9 C
    
20.         int[] temp = new int[right - left + 1];
    ) J; k7 b: W, N
21.         int i = left, j = mid + 1, k = 0;
    5 f# A1 Y# p( g9 Z1 o! Z8 P* g; C
22. 
    * O/ P4 Q\" Z$ [) \0 B- T
23.         while (i <= mid && j <= right) {
    4 t\" w; D* v7 `* K
24.             if (arr[i] < arr[j]) {
    - l: o1 G4 ?5 q
25.                 temp[k++] = arr[i++];
    - d8 L9 g1 t2 S
26.             } else {8 n7 `& B, T% h* `! L: v) m
    
27.                 temp[k++] = arr[j++];. P: ~$ m  e  S- S0 T
    
28.             }7 A4 E; z+ [1 M) T
    
29.         }, ?) S: I% t0 w9 X
    
30. 
    % b\" v) P. E% l9 F; p
31.         while (i <= mid) {
    * H3 P; ^6 u$ H8 I+ h! _( X
32.             temp[k++] = arr[i++];
    ' {\" [# U1 I# }9 w6 w) Z2 b
33.         }
    3 }5 V' r2 p# E
34. 
    0 u9 A- }; S) c: d; w
35.         while (j <= right) {5 M+ n$ X5 J1 R: B
    
36.             temp[k++] = arr[j++];) T; Z) e\" c8 y8 M. J0 Y4 N
    
37.         }
      p. C( z- M2 u# v. a; @
38. # y- b+ C/ t1 W' P& r
    
39.         for (int m = 0; m < temp.length; m++) {. [* f, W* |, I# Y+ l! N, I- B
    
40.             arr[left + m] = temp[m];
    . }- n4 R0 N9 c' n9 |
41.         }- n) y4 n9 e% G\" ^! Q7 e9 ~
    
42.     }
    ' M' {7 T+ G* o  g5 z
43. }

复制代码

这个实现也使用了两个函数，一个是 mergeSort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。

下面对这两个函数进行详细讲解：

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   # d# U, V) W# F' ^
2.     if (left >= right) {
   0 j6 O2 o6 c) P: m
3.         return;
   4 D# z; N: W+ @  N  G
4.     }$ `0 k7 |9 o  K; x5 l
   
5. 
   ' d7 ~$ ]& W' i( k( S& E6 M
6.     int mid = (left + right) / 2;% V1 m1 q1 Y$ H4 k
   
7.     mergeSort(arr, left, mid);' V: {6 ], a9 }
   
8.     mergeSort(arr, mid + 1, right);/ g# R4 x9 Z# W1 ?; s. R
   
9.     merge(arr, left, mid, right);7 M0 E6 {6 N2 C( S9 I
   
10. }9 s+ T5 X* s% X2 S; J
    
11. 
    , q3 i% T! ~$ f& P0 f, T

复制代码

这个函数使用递归的方式对数组进行排序。

/ K8 {7 E7 Z3 X3 [- [& h! I对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
# ?( b  r2 c# ^$ M, d
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {) K4 n9 a1 A/ L/ C: `3 ^- t
   
2.     int[] temp = new int[right - left + 1];
   & o+ v5 }* p, V+ Y% `. p
3.     int i = left, j = mid + 1, k = 0;) n/ g5 [1 S( B) b' E
   
4. 
   4 J1 o) m9 i/ q% r6 E0 R  T9 S
5.     while (i <= mid && j <= right) {
   + X% Q  Q! G# _/ W7 l# b) x
6.         if (arr[i] < arr[j]) {2 u6 [5 w) u4 S: |0 B$ Z: J
   
7.             temp[k++] = arr[i++];
   1 U5 y$ K6 ^5 d( F( X\" n; S
8.         } else {
   ! m* c\" |+ Z' w, A9 S% f  {6 e
9.             temp[k++] = arr[j++];
     {* x' ~7 q9 _  H4 i* U
10.         }/ o2 y; Z& Q2 w2 p/ w1 H2 C2 g
    
11.     }& r/ m7 C: V3 W3 b1 H$ t! v1 A% C
    
12.   S3 K! n; @! l, U: i9 o+ g
    
13.     while (i <= mid) {  N  q' M& k( B- X9 \
    
14.         temp[k++] = arr[i++];
    ' w' y' m  X* r
15.     }
    5 F& d$ D& o- a! z2 a. w! s2 i) N5 r
16. 
    0 o* M* r) G5 r2 @
17.     while (j <= right) {3 O# {5 P' G$ }, X. y: Y/ M* u  c
    
18.         temp[k++] = arr[j++];4 S$ o! F9 F. o8 ]
    
19.     }5 O6 J. Z, y6 K% E& o1 k
    
20. 
    ; |( J, [* y& @1 f8 V) X+ z% q
21.     for (int m = 0; m < temp.length; m++) {
    2 U( M0 e\" f* {; M: G! |. i
22.         arr[left + m] = temp[m];
    ' H  g( ~2 O- [* K8 X7 B/ ~
23.     }) N0 ]( u, D# W0 b
    
24. }2 I1 E9 o6 C! T\" a
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。

) v, r1 H* ~% h: Q+ |合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
$ r4 L6 M( C$ d5 L. Z
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。


+ X. [2 W% Q7 I: h/ h" J. B9 Y
! R/ D/ l6 c) r* ?
* {! \# U/ r! U. H2 ?4 B
$ c+ P/ J# @0 Z. h7 T& l
' R+ C/ ?. M' j7 `! F5 d