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

2744557306

1 基础介绍
' t2 B" u  p" ]) ]; p排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
5 e  S* s( O0 u3 x2 R: G" }
以下是一些常见的排序算法：
) U( O7 i5 i3 X2 p
冒泡排序（Bubble Sort）
/ a) l. D) Z5 X( S: i
插入排序（Insertion Sort）
8 g! O! B3 w3 l% p
1 d' v& g! S1 {1 w' ^  o选择排序（Selection Sort）

, \" n7 C' S: m归并排序（Merge Sort）

9 ]" N2 T. j9 L快速排序（Quick Sort）
, k' q5 Z. x8 M9 V
堆排序（Heap Sort）

5 G' h) Q) S: A" d) R一、基本介绍介绍
9 f* ]$ q3 ^, W$ c  W0 ^. C% O5 `1.1 原理介绍
/ |: X: P7 Z2 S/ j归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

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

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
& M& T- E, {9 W% L! x% E
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
- q- W/ j) D% a" h4 e
  M! O8 ~6 h# C合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
1 i0 A& j6 `9 e
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
, P5 ]+ _7 j: z2 F$ ]2 q
4 i; l) b" K3 I2 ~; ^: _3 A比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

& m" U4 K: a$ ^1 z6 U重复步骤 2，直到其中一个数组的元素全部放入 C 中。

* ?3 m1 I  X; m& L1 y2 I% h, F! v将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

# @8 M" G8 v: i原理简单示例
/ w; b6 h% u6 p3 U4 f5 v以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
( f! G5 G( f/ _
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
  Q, v% R8 z8 b/ e0 k4 j
" w; w' u/ U' n: F9 w1 W# x) o" n首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
) n( p& ^3 r* b$ ?
- q5 ~: M2 \' I: i  f! Q对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

, J1 I$ \$ z5 t$ V$ `* H* l对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
. z3 Z! J! ~) T7 y2 b8 g1 i7 v
+ y4 n( ?/ L8 l接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
2 [& V5 T0 i( }3 H
/ U3 M9 |& o7 C9 n将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

9 ]9 y9 z2 Z2 ^8 `- E8 i0 w$ N因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
: p& ~; _$ d, G% H2 W, B' s
1.2 复杂度
6 @* h/ {- S5 c* m" N1 Y归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。
# _' i6 F( U% V& V$ R4 e/ M( P) L
! z& y2 p+ U2 X7 g首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

8 y% T& t3 Z9 E+ s归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
5 K5 x( c, x# O8 \* ^
8 a  l8 W5 f2 r2 V这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
$ d; |3 G, i6 f4 u0 ~归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
0 R: s* @1 ]3 o$ M' [
" c1 u" q  c3 \9 l5 {- _6 ]- P对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

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

2 W8 L, p. I, C# J对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
3 Q2 \' I2 a; l" N2 ~2 {
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
' L1 D8 [: r$ ]) {1 N" t
二、代码实现
& ~; }" A# q3 y, V  v4 I2.1 Python 实现
% y/ s4 z" `8 A以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):5 ^% u; x3 E$ L/ z
   
2.     if len(arr) <= 1:' n: f5 P- V# ~
   
3.         return arr2 S8 \3 f/ j- m7 l; P& l
   
4. 
   % b; _, c; h1 p6 N: H! z; i; H# O
5.     # 将数组分成两个部分. t2 \' }  _6 b\" f7 v/ T8 i0 H* ^' q* \
   
6.     mid = len(arr) // 2
   0 y\" B5 h& \( ~( P\" \
7.     left_half = arr[:mid]- Y& J) h5 u! f' ~0 |6 N, X# a
   
8.     right_half = arr[mid:]! G5 u3 e0 e6 p5 g\" I% L
   
9. 
   - L# ]0 W/ ?( H2 G4 w8 N9 U
10.     # 对左右两部分分别递归调用归并排序5 U6 k6 g9 A$ ?( R) U* W
    
11.     left_half = merge_sort(left_half)
    4 g5 J- m/ H8 c$ Q6 {\" R; ~! X
12.     right_half = merge_sort(right_half). r9 D. C7 s  L- L  ^1 p6 g
    
13. ! e; _# Q' F9 n% _9 x- |
    
14.     # 合并左右两部分
    + j  A5 }0 L0 s1 I$ n
15.     return merge(left_half, right_half)3 z/ w$ I- W, d% V! K8 z
    
16. 
    ; x+ _, q3 g; x; o% X
17. def merge(left_half, right_half):
    - T( z3 m9 d* ?) v% E' e\" V
18.     i = j = 0) N6 d$ L) b) Y2 w. N
    
19.     merged = []5 n, r1 ?$ t# T* _
    
20. 
    / C+ |5 K+ x7 S3 T
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中7 v0 S\" L4 T& M1 P  }
    
22.     while i < len(left_half) and j < len(right_half):) f1 _' T\" w; ]* p; a: W0 m1 a
    
23.         if left_half[i] < right_half[j]:; l  t8 h  t* P, d. j: f
    
24.             merged.append(left_half[i])
    ) _( u* B* B  J
25.             i += 1
    : i\" s5 E4 C6 ?\" {# w/ {  w
26.         else:6 [3 y; D! {! ?0 J  m: f
    
27.             merged.append(right_half[j])/ Y7 n9 b5 y\" k: Z) D. P4 z* q
    
28.             j += 13 g4 p$ A  j: h! X
    
29. 
    8 z7 ~5 g9 e0 G
30.     # 将左右两部分中剩余的元素添加到 merged 中! A3 y$ M) U! Z5 f/ ]9 T
    
31.     merged += left_half[i:]
    ! H' ?2 |% |4 ?9 F; Z+ A
32.     merged += right_half[j:], w( J( _! }. ^) A2 r8 h\" ^
    
33. 
    % i  c. W# O2 B' Y: h
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   7 v/ A\" x. _3 K; }: P, h5 q
2.     if len(arr) <= 1:
   7 k6 n  R2 Y/ [; r7 A) F
3.         return arr
   4 `. U9 d' Y' p; ]8 M
4. 
   ' ~% K: I8 B\" E6 G( @  `/ m- a
5.     # 将数组分成两个部分# v) x8 J/ H\" s: m& f
   
6.     mid = len(arr) // 2) k) r7 u. U# m\" k$ R1 u/ p, U
   
7.     left_half = arr[:mid]
     ?& e* Z) f( `' q' O) [* }
8.     right_half = arr[mid:]
   9 h! |5 [0 V' u
9. 
   / Q4 v. [: a\" v% Z4 R* Q
10.     # 对左右两部分分别递归调用归并排序. i3 _+ I/ p2 y3 }' v) l
    
11.     left_half = merge_sort(left_half)
    \" r. Q% U* L6 r9 M* @/ D9 x, o
12.     right_half = merge_sort(right_half)! l2 {1 S% S: F% C' u: P
    
13. 
    ) W/ j. I! a5 J0 O; T! l4 |& l
14.     # 合并左右两部分9 G* \' Z7 G0 T9 L/ d9 P) S
    
15.     return merge(left_half, right_half)
    $ L, A8 |4 ]  O% O# b+ x. J' z- v
16. ```
    $ X! ~/ g: c\" i3 X9 V
17. 0 z' b# d3 }% V7 b# D4 `\" h
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    ! ~, F/ i$ s& R% b1 t5 y3 K

复制代码

merge() 函数

1. def merge(left_half, right_half):
   , w' X+ E7 v, Q0 f\" T; T
2.     i = j = 0\" S! J$ h( Z' k' y% i3 U; ]% ~: U
   
3.     merged = []  B: p+ ?9 b8 ?( c6 \) ]
   
4. 
     Y/ S/ t9 m: f\" `$ n4 K+ [
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中0 O7 _! E+ u; Z9 r
   
6.     while i < len(left_half) and j < len(right_half):
     v  F7 s\" m0 M5 x7 A2 q
7.         if left_half[i] < right_half[j]:/ M4 f- `' Y/ @% l8 |
   
8.             merged.append(left_half[i])
   ! o( l! |# A9 m$ i/ H0 r
9.             i += 1: v( b- p/ M8 R. D3 f3 W6 e0 ]9 W
   
10.         else:
    ! a% y! N8 X2 A\" ]5 D) y
11.             merged.append(right_half[j])
    0 I0 y' O& J8 D2 |* |. ~
12.             j += 11 f$ z( P' R. `9 A
    
13. 
    3 H8 U2 g! w: k' L3 a
14.     # 将左右两部分中剩余的元素添加到 merged 中2 B4 r, \3 f! p4 K  {+ i
    
15.     merged += left_half[i:]
      w/ B5 W* R$ ^, o- K$ l; ?
16.     merged += right_half[j:]& D& \1 J* ^$ C\" ~$ R4 H1 L
    
17. . K5 k; M: @  t( K/ ]8 \8 m
    
18.     return merged
    ' C; P1 d1 e# \- P$ v) @' @0 \
19. ```
    - x+ _5 c; g\" i, V0 F- V/ W
20. 
    9 [; t6 S; M\" N, \4 v; D+ _
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

4 \- h9 }0 }) ~* S9 C/ |# \判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
  t/ g, ], V( D6 A5 }
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
* R7 a- x% b" d( v* D& Q
/ j5 i' _) P% Y4 q7 M- ^合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
) L# E7 e1 K9 {% R+ m* q
: `" E3 |- `/ x: X. u6 a" K测试
2 W$ q3 i( j% @0 ?0 v在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
     }, e$ \4 m5 j
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {
   9 {( ^8 }+ e* G( X8 ?\" A\" W; I( C
2.     public static void main(String[] args) {( p. p  r! A% `; Q1 ]
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   % @, G% M; m* T5 _
4.         mergeSort(arr, 0, arr.length - 1);. k* |' ]\" G6 ^9 t, m: F
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   3 g2 e! H/ W3 A  L
6.     }
   ; \& i# T' ?' V6 ~9 L3 s
7. $ W& ~( S  h& w# N8 C: N) U9 P; K
   
8.     public static void mergeSort(int[] arr, int left, int right) {: B- j6 [) ^; j9 m
   
9.         if (left >= right) {  X% z( I' l2 m\" O, \1 y
   
10.             return;
    # X; \# u( U! @6 [\" E
11.         }
    6 g% w, ?& L* I. Y3 S
12. 
    , c  g\" n1 ~! L$ ]/ F
13.         int mid = (left + right) / 2;
    3 ~, [5 k, @0 n9 }( {/ s
14.         mergeSort(arr, left, mid);9 l6 h1 z- i. w: s. W! R: x  j3 Z
    
15.         mergeSort(arr, mid + 1, right);
    - y/ w' w  Y% J6 Y& ]4 {+ ^' D' K
16.         merge(arr, left, mid, right);
    & A: b. _1 z8 \5 U# J
17.     }5 n: I* N5 ^2 ?' F; [0 v
    
18. : g( i+ _: w1 T2 n! g
    
19.     public static void merge(int[] arr, int left, int mid, int right) {+ _/ A( C+ I% ^8 x/ y
    
20.         int[] temp = new int[right - left + 1];. E( M6 b* Y8 u% P0 e0 q
    
21.         int i = left, j = mid + 1, k = 0;
    2 ?. @3 V\" S9 L) I9 {
22. # J3 T% t1 t6 g, l
    
23.         while (i <= mid && j <= right) {; `( `( x, `# R) u5 {
    
24.             if (arr[i] < arr[j]) {% I; w4 \' Y5 v
    
25.                 temp[k++] = arr[i++];6 T+ l3 r9 o\" Q- [8 x4 g
    
26.             } else {3 z5 [6 G& p* H# _+ u9 _4 n# A
    
27.                 temp[k++] = arr[j++];
    2 r' s% z# K6 O  W
28.             }- |' p: j\" o( Q) }/ Z% }
    
29.         }4 m9 Q' N% o5 e' H% M! z) w) u4 r
    
30. 
    0 F% C( c2 a. ^3 b# w# |: Z
31.         while (i <= mid) {
    & O) M3 k3 G  k
32.             temp[k++] = arr[i++];* ^( p  j- a1 |6 y8 W4 P, f% O
    
33.         }' z3 U9 I4 s% s& G2 A
    
34. ' A' B( ~0 ]0 }- `
    
35.         while (j <= right) {
    7 w% R( |$ C- A* X0 z# s; y# }
36.             temp[k++] = arr[j++];
    # o) k3 a/ Q# z$ @$ [- U% d
37.         }3 _7 z0 I/ C' S
    
38. 9 m8 N/ ]0 N0 G- Z
    
39.         for (int m = 0; m < temp.length; m++) {
    0 ]! L5 z/ o; X) v3 i
40.             arr[left + m] = temp[m];
    2 z2 x9 L8 r: N% i
41.         }
    : o/ J6 R& u; A! u) ]6 \
42.     }6 r5 M6 }* F* I' r: Q9 f) ~. x
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {\" C! k+ z\" q: N* V! p  ]
   
2.     if (left >= right) {; \  h4 K; b8 g( P- `9 r$ c, J! C2 p
   
3.         return;
   . m2 R8 M+ F$ k
4.     }3 Z; J5 W1 Q8 G5 p
   
5. 1 @4 P) `9 y  i3 L$ f* A
   
6.     int mid = (left + right) / 2;
   0 `0 V! S: y) k* \
7.     mergeSort(arr, left, mid);
   : n/ v; ^8 I1 D3 [& N\" ?
8.     mergeSort(arr, mid + 1, right);1 X: H0 Y! F- W$ b
   
9.     merge(arr, left, mid, right);
   + i+ z* N6 ~9 Z4 ]
10. }
    * Q! X* Q# p9 O# O  y
11. # v' {) N  @& x' B
    

复制代码

这个函数使用递归的方式对数组进行排序。
4 y3 w1 I7 w( t/ n% B  U  }
4 K* X2 s- w% m. B7 m对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   6 F6 w# f# h) y. Z  l- A5 G
2.     int[] temp = new int[right - left + 1];* w) r0 y/ p6 X
   
3.     int i = left, j = mid + 1, k = 0;
   5 y( N, \- x  O0 e- E, a* `
4. $ P0 u4 n9 g1 |\" A! A/ f. [/ F6 T
   
5.     while (i <= mid && j <= right) {
   * f6 \3 ~6 ?# R) q\" a
6.         if (arr[i] < arr[j]) {
   ! r$ \2 n! V( k( l1 _) R
7.             temp[k++] = arr[i++];
   3 i/ S. x* P' E5 _* N- s  V- V- F
8.         } else {  V8 ?\" U+ a# P  d\" u$ n: I7 r. ~+ I
   
9.             temp[k++] = arr[j++];$ N* Z- K+ q, B. A) A8 D0 x8 P
   
10.         }
    : z$ O# O& l4 v8 q
11.     }
    ; k5 E! [( R# ]+ d& w1 _
12. % S. K% a- N( c  G6 j2 Q2 J
    
13.     while (i <= mid) {\" v. O\" a) ?+ y& e+ J* O6 f
    
14.         temp[k++] = arr[i++];% K' z4 X# j! G6 i\" f4 Q( M\" [$ `
    
15.     }
    6 _8 _5 Y$ J$ F& r- I
16. ) b/ [; f7 g5 d4 t9 T% p
    
17.     while (j <= right) {
    - A5 ?* l5 P% _9 w2 T9 p% _
18.         temp[k++] = arr[j++];7 z$ M3 n2 b7 f  W  P
    
19.     }
      o1 @3 `. C1 z# X\" c
20. 
    3 P9 N. D2 K  R
21.     for (int m = 0; m < temp.length; m++) {: Y) }. X9 n9 y: Q2 c; D3 b& F
    
22.         arr[left + m] = temp[m];8 M9 @6 Z( ~4 u. _
    
23.     }) G- q6 O. [3 [3 S
    
24. }- I0 e  x) ?& n
    

复制代码

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

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
) E0 U; e" |1 g2 }
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
( q. |1 s5 W& d  y; b# f
3 L, `( t, ]1 V3 E6 \需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
, i+ J( s1 p( C# |5 N0 M
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

0 u6 f* E' `. c
9 `3 }7 [, r, \0 L



2 W; K5 Y+ C3 Z6 m4 k/ |
9 `+ m3 T& G- C4 h0 O