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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

6 S7 w8 P1 G3 e以下是一些常见的排序算法：
) M1 E* @6 @) l& Z
冒泡排序（Bubble Sort）

1 i* `3 O6 ]% v3 a, e6 a1 X插入排序（Insertion Sort）
2 [9 T0 t& ]3 O9 @9 Z" [3 n: Q
) F: d1 A, t2 N" F7 I/ ^选择排序（Selection Sort）

归并排序（Merge Sort）

! C2 Z. Y' B/ F' y快速排序（Quick Sort）
! q7 I; @5 K+ q$ j
$ j2 S+ U/ F: x. R5 f堆排序（Heap Sort）

. F$ S8 ~1 x; v0 ~5 V+ N" j一、基本介绍介绍
. `7 v8 J- G  V+ A6 p0 P1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

# U  m) H! |& u9 F! q归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

% |0 z" L" l+ K8 b' [' [. L" P分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
  ^- y+ J, s$ b8 ^
, [/ P8 y8 I5 q! |合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
) V! W, ^( h/ m/ z! a( W
$ W+ Z! k& ^! _比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

+ `+ E3 ~* c' a5 Q重复步骤 2，直到其中一个数组的元素全部放入 C 中。
/ a8 w. C$ z) q4 u+ T4 z9 r
将另一个数组中剩余的元素放入 C 中。
& k9 E. j: O6 t% `
" ~& M# r4 o3 ~: ]归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
7 q, [; Q& L; B2 C. V/ n9 s) |/ ~
原理简单示例
/ y' f0 O, U! ^7 d0 ]以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
* m+ X6 G7 w( Q2 h- b* l6 M
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
! d6 p4 F. o6 K
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

4 }: w8 v4 C; Y& D" d  A对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
3 _. u2 Z. G( ?+ j6 T$ S4 Z5 ^5 U
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

3 w& z7 L! r; o3 U将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
7 r4 a1 k8 L% c8 O
# f2 y* }) @5 F# O因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
5 A) w* E0 l8 b. ^3 D9 g- g
/ W+ @  G/ H- J/ V7 I1.2 复杂度
% q  n, x5 n/ n归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

+ _) m" k9 E8 d0 M这个复杂度可以通过分治的思想来解释。

2 ~1 T/ k( h9 k首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
+ `7 v& N! Z, ]+ n$ a- j
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
7 g) }9 r& ?0 ?; s+ ?' r
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
- M: h' v$ q% [% D) H
2 p6 q, S, ?5 J0 {1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
& q& l$ l/ \- X, k7 W' M' N# Z' W$ I
对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
) n6 Q/ O  ~/ x: k* z
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

# k; b3 h; W$ i- m" ]0 Q对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
# i; c" _. B! \- D! I1 i- I/ ]* k4 A
0 c) {+ }, ^, {总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
  a5 Y) @& M& `; I* j7 z$ M
二、代码实现
( @5 `8 o% i% G: f8 X2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):+ L; Z# P3 ?  y
   
2.     if len(arr) <= 1:( P+ U& w2 P2 f; {
   
3.         return arr
   2 l* P6 R# x& F6 P& R4 B
4. ) P6 h. a5 G* z0 C$ f; i6 \) y9 j2 ^
   
5.     # 将数组分成两个部分
     d( H( [\" h  z. @5 A5 \0 @5 P
6.     mid = len(arr) // 2, R  v' r; |% e  u% N7 b$ }( T
   
7.     left_half = arr[:mid]
   + V. ~  a! e- q6 D- {
8.     right_half = arr[mid:]
   6 i8 Y, s, i/ {  y6 q& ~5 s
9.   p! E. g7 k0 F. }
   
10.     # 对左右两部分分别递归调用归并排序% C\" v1 Y; ?. _1 u1 X
    
11.     left_half = merge_sort(left_half)4 q+ Q* I7 X8 R
    
12.     right_half = merge_sort(right_half)
    # h  L8 b  M# a& @4 K* u& _
13. - g& l# k2 g* s7 o+ }3 {
    
14.     # 合并左右两部分
    + {) Y' @! a1 T& p9 d* j5 W5 [
15.     return merge(left_half, right_half)
    1 m1 q. y' V: C: T
16. ! V4 m2 Q) q$ V3 U/ q; U$ z1 D
    
17. def merge(left_half, right_half):
    . U, N9 Q3 [4 |6 I5 `
18.     i = j = 0; M, G4 p! `, G2 l; |2 K
    
19.     merged = []
    & e% j! P9 }  y) [8 j
20. 
    $ E# @$ l\" e. d& F0 v
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    4 B* j. ?1 S8 f+ G
22.     while i < len(left_half) and j < len(right_half):
    3 i$ l\" V2 @. J8 n7 y( h
23.         if left_half[i] < right_half[j]:
    ' ?& S3 [- R+ _) ?) S& @
24.             merged.append(left_half[i])\" {' Q7 ^/ F' G6 C
    
25.             i += 1
    ' n+ w, p  \/ V! p
26.         else:1 G- Z# K3 b9 t4 M
    
27.             merged.append(right_half[j])( [' U+ U( @+ T1 K/ o\" v
    
28.             j += 1) n5 Q; b0 K. w0 ^0 p
    
29. * X5 P4 F+ ^  J' O9 P
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    - I* `! i/ @2 c9 T+ h$ ]
31.     merged += left_half[i:]
    ' G9 \% q! N5 F  @\" H: g% P
32.     merged += right_half[j:]
    % E, {' G* n% Y( o& y$ y! _+ h$ q
33. 
    0 w\" _' m; q* B+ T2 _
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):% p% I) `1 V& b0 K2 G
   
2.     if len(arr) <= 1:
   ) x8 q/ N0 c9 t  {. x8 C
3.         return arr
   & K! F* b# s; {$ d. k# a; D
4. 
   $ b; Z. i1 k: _
5.     # 将数组分成两个部分& J' o! l& B9 L3 J
   
6.     mid = len(arr) // 2. N7 m; k4 Q' H3 ~9 w9 v- \
   
7.     left_half = arr[:mid]- o% S0 n7 s; Q) m  ~3 t6 X
   
8.     right_half = arr[mid:]
   9 C( h4 Z* ~& I; B9 m; y
9. 
   0 Y( o! e' Q2 _\" _1 s( X
10.     # 对左右两部分分别递归调用归并排序! g# T; E( T! H8 W9 F: i/ d  d
    
11.     left_half = merge_sort(left_half)+ m! B7 [5 J0 h) l8 f7 @1 _+ I9 v. m
    
12.     right_half = merge_sort(right_half)% Q/ n# Z# t& O  k
    
13. 9 N) U/ }. }\" f6 C5 a1 A
    
14.     # 合并左右两部分8 Z: e- k1 p8 N+ ^* D0 Q& h
    
15.     return merge(left_half, right_half)
    / v' g5 r8 y* _+ J% c8 [
16. ```
    ! x6 x5 s. g\" `  p! a; ?' `# e
17. ( a1 k. T& l. {
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。5 N, J3 M  ~) q/ \5 A+ `
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   8 [  t% _# m' ?; k+ I! `7 l
2.     i = j = 0$ F9 ^+ Y* n; n5 T' U
   
3.     merged = []
   $ Z$ p: s3 `9 ^3 Y3 t
4. 2 v( ^2 v7 g8 Q$ E  A: K/ `
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中3 q6 ?  B2 I/ C0 i\" V; E
   
6.     while i < len(left_half) and j < len(right_half):
   3 J! d- ^5 j$ R5 L
7.         if left_half[i] < right_half[j]:
   - E1 o- e$ S- S8 f! e
8.             merged.append(left_half[i])
   8 Q5 H4 i* [! k+ E\" E
9.             i += 1* N8 x' D; d: C' N/ @1 @. F
   
10.         else:
    6 m, X  W2 l! x9 v; ?7 B, _
11.             merged.append(right_half[j]), j& r4 x' ]  `- s9 y, |
    
12.             j += 14 U2 l! @' B# }4 y$ |% h\" n. R
    
13. / L- t6 r4 R: `' i% W& f/ j
    
14.     # 将左右两部分中剩余的元素添加到 merged 中& G$ M& s4 }5 P5 C4 |& _* ]7 U9 _
    
15.     merged += left_half[i:]
    4 m5 S2 g0 l5 i
16.     merged += right_half[j:]2 }1 x, E9 u' V
    
17. 
    9 I6 K1 O8 x\" a% X; ]
18.     return merged
    8 i1 Y8 e) O+ a$ K/ U3 s+ x
19. ```
    1 K4 n; I9 x% i& q
20. 
    ) [! a\" q% u0 e, b
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：

# h9 ]$ M( N9 z! U) X4 s7 k; r判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
6 _6 l7 @" ^0 `# p- n- ^
( }, j2 I" Y7 {1 F对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
( e. A2 [2 n, A
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
, ~$ Y% \3 O& ~
" E! E; m# x* T' L8 R测试
% K; v' u6 @# _* p2 c在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]! r6 W0 }7 H, ~( E  s% V
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
/ a# k) X8 O# j% d! a4 E
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {7 n: V: M! ~  Q/ k; ^7 O
   
2.     public static void main(String[] args) {
   . y& A! X& j2 n0 h\" ~! a- ?8 w
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   % [* ~9 W9 \& g& a8 @% a
4.         mergeSort(arr, 0, arr.length - 1);  C, x' g' \) m: K( M& S3 _& y
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   & D) y  B: o& g' S3 `+ G
6.     }( c6 q9 w3 h9 H2 s! X\" l; I
   
7. 
   \" X* x$ V: B1 B  P% e, `
8.     public static void mergeSort(int[] arr, int left, int right) {
   , s) s. B# A: h1 x6 N
9.         if (left >= right) {
   . \& U& x- A+ h/ G& X4 @\" C
10.             return;
    6 n0 z2 O$ a0 H( R
11.         }& Z' T9 f) g5 z6 [4 I( a
    
12. 
    / T4 \) `5 ^' J- g* ~
13.         int mid = (left + right) / 2;9 J- j7 j# D  c, G2 f! o
    
14.         mergeSort(arr, left, mid);6 ]  z; L6 o0 a1 ?, H4 E  ?5 d
    
15.         mergeSort(arr, mid + 1, right);
    7 Y\" L2 K! q) f) f4 c4 c; h; x
16.         merge(arr, left, mid, right);& R4 s9 K/ \1 a& H# c. e
    
17.     }, W7 d+ c& i0 `9 ?\" D6 s3 t
    
18. ' y( S. y7 e/ ^. J) o- Z% p' H
    
19.     public static void merge(int[] arr, int left, int mid, int right) {1 \$ Q0 f: H# e* ^1 u
    
20.         int[] temp = new int[right - left + 1];* O0 H2 V! N/ P% ~
    
21.         int i = left, j = mid + 1, k = 0;
    ( j\" C' V/ T+ |& g! {0 w
22. 
    / ~0 K# f% q1 {7 U* ?, `% h
23.         while (i <= mid && j <= right) {& z# r: s0 T) N- j7 p+ m+ ]# y
    
24.             if (arr[i] < arr[j]) {! t% K% U' e1 x\" Z  D( D
    
25.                 temp[k++] = arr[i++];: d/ f8 {! I; @6 }  ]. _
    
26.             } else {  X8 E& ~+ \5 G0 c( j$ D
    
27.                 temp[k++] = arr[j++];\" \1 A; l. F# x* E- j* i; w. w
    
28.             }8 `0 U3 F4 ~( c, @0 J3 w% Z+ j  y
    
29.         }; t8 F2 s  g9 |- K& K( y0 a& w2 x
    
30. & R& ?$ d5 x0 N
    
31.         while (i <= mid) {* i* }2 M& H. ~\" L
    
32.             temp[k++] = arr[i++];
    ) Q9 \6 B$ L/ d) z4 P$ l
33.         }
    1 f3 E2 e0 C5 D% }
34. \" q2 _# {9 \. @  E% T! B
    
35.         while (j <= right) {
    ( N% g; m* Q& ?6 H  a. ]
36.             temp[k++] = arr[j++];
    6 c( m1 E( g2 O; ~0 e& v9 G
37.         }
    7 H# T( e# g/ H. R$ \( {: ?8 Q
38. ' z/ j\" q  F. e+ l
    
39.         for (int m = 0; m < temp.length; m++) {/ V& Z, D' ~& K/ ~+ v  N4 l2 D
    
40.             arr[left + m] = temp[m];( @. l. `: k8 p5 E  V4 l. m& O
    
41.         }  p( y0 K+ G; b8 q2 F. R
    
42.     }
    \" F! p. D* ~6 B% A
43. }

复制代码

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

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

" H! |0 F- u2 w+ C6 t1 i' DmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {\" D) ~5 c* d/ T9 ]\" `
   
2.     if (left >= right) {
   $ y8 M2 e! s( P
3.         return;
   0 R- ^\" Z- ?. s. \. z. D
4.     }
   ; O4 _7 j# E5 `
5. , j1 N  ?7 M! V6 q- i- ?! ?0 s
   
6.     int mid = (left + right) / 2;
   , @/ A4 N- k. L' Q: _, [+ ^
7.     mergeSort(arr, left, mid);
   # L, ~0 [+ `6 U: ]0 M1 Y( ^
8.     mergeSort(arr, mid + 1, right);. @8 K. M: T& R( _* K' ~* t
   
9.     merge(arr, left, mid, right);+ e' ^+ x; w+ s
   
10. }
    $ }  t& e6 j, j) [
11. 7 T* M- L* @2 D
    

复制代码

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

# h$ T( ]9 \; _) W, W* J: E8 C, W对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
5 d+ ~0 b6 G8 J$ _/ j$ S
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
4 G* Y8 }1 f! G. k$ Q3 X/ rmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   ( c8 Q% F% K  H1 q( {4 T) n
2.     int[] temp = new int[right - left + 1];
     ?8 K5 m7 P! n2 }9 y1 g- i9 `
3.     int i = left, j = mid + 1, k = 0;
   9 M7 s, }. l6 `. h
4. 
   % p) [: g4 p& m% Z2 x) l8 p
5.     while (i <= mid && j <= right) {
   . H4 n$ M6 v) o! b
6.         if (arr[i] < arr[j]) {
   8 t6 W- k# _- g\" q\" u; Z# i
7.             temp[k++] = arr[i++];7 X$ t. M! S! T6 r7 W4 I1 Z- D+ w
   
8.         } else {; }% h* J9 D# }/ k8 _3 w
   
9.             temp[k++] = arr[j++];
   3 Q9 |2 }' u0 X+ o+ E
10.         }  s6 h- |0 s& \
    
11.     }  P2 K- O\" y7 ~5 D: K; t
    
12. ; G6 y& q; X' n3 |7 b
    
13.     while (i <= mid) {
    # w9 n& M+ F6 W- E1 v
14.         temp[k++] = arr[i++];1 h3 X5 ?6 ~& g- g! L4 T) D( ~
    
15.     }' H4 w* C: q  i
    
16. 
    9 h3 @% X8 h& o; V* x% }: M# Y1 ?
17.     while (j <= right) {- I, P3 y( M& X+ j6 x* A, v
    
18.         temp[k++] = arr[j++];# k4 ?& I4 N9 R) Y; U
    
19.     }- B\" ]+ M, a' Q! B1 H- S
    
20.   c( R$ K( i! |6 v- u! @
    
21.     for (int m = 0; m < temp.length; m++) {8 y' B. w/ g  B7 L- Q, G+ ]
    
22.         arr[left + m] = temp[m];
    1 u7 Z8 B% c1 L& D
23.     }
    ! B) D: F# j$ z4 |3 _# k  g
24. }+ b7 Z+ B2 M2 a3 V- n# V, n
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
. E2 B' _; c! i0 z8 d+ s
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
1 O; E6 W% ~/ I
需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

; I. [  C- J, a- q( |  ]" c这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
& j% q8 k# b$ W' L( s$ c3 G, q4 N



! U4 C, P+ E- p

9 ~8 @0 C1 P* A