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

2744557306

1 基础介绍
0 j9 O2 g0 s+ @  O) U$ h排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

% c- r; E' g' L& |以下是一些常见的排序算法：

# T! Q* G4 L6 |) A. Y  m冒泡排序（Bubble Sort）
: N3 r' h3 M  ~& G' b0 X6 ~) o
9 V7 b5 b3 A9 E$ n+ z插入排序（Insertion Sort）
) K9 _: [6 {. `! P. F
选择排序（Selection Sort）
$ r. {/ j5 ]" L9 O. X1 m% e9 z4 p8 q
归并排序（Merge Sort）
: t) l( h6 N' D2 a. r6 p1 _  O# U
7 g/ E$ M3 q+ t) a$ O: }快速排序（Quick Sort）
; d! m; G, p) j1 o& _7 e8 N
8 e8 O' d9 v9 i$ ?, R2 q堆排序（Heap Sort）

一、基本介绍介绍
' g- m  I: [! V, i+ j1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

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

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

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

+ Q% v; X) S: T: \  |9 y比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
1 u5 A9 Z$ }8 u
重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
# N/ k2 g3 i% k$ x: w
# O- j6 {6 I; s归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
7 E+ d$ K# e; u6 {1 U) a) I: M
! J, k4 V5 X6 [0 u2 p* b6 S( j原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

. P/ J" N" R' u' N" T% g  m" K假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
5 J% h; v7 z! _' N" p
  y- r/ d7 F8 @7 X首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

0 j9 W- [$ U0 J) }) K& Z6 J, t4 u对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
" U/ @  [1 W) c5 q2 m
将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
  p. D2 R* b; J+ W0 x% U, w. B4 N
2 J, r% `* g' k- i6 C因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
; i4 {$ a3 h3 n4 q$ E9 `
6 v) f# K% g$ P* R  E7 L+ P1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

" U8 F) \' J: p1 ?- u5 r3 N5 z4 q2 f这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

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

+ H6 d8 f) k) W归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

! D- I: q# C. @+ O! {8 |这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

& L( D% S4 ?& K, b1.3使用场景
( y0 U# L7 K; r: B) B3 a# q& s$ k归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
5 H; {( _. c" b2 P# P/ r6 c
5 t1 h* c' y% B0 S对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
3 Z( Q7 q* w' D& l
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
3 h( S5 N1 w% y+ g
& l0 X1 L1 r4 G( ^& {8 d) T! d对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
& T! q- w5 L1 u3 E
: R6 W. Z( ^0 _  ?& c  ^% a$ c总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
( ]) N- J8 c- O8 }/ f! U
二、代码实现
2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):5 `- I) W0 o\" t3 d/ ~4 U$ Q
   
2.     if len(arr) <= 1:6 e& S# g7 m& Y2 U7 c) `; v0 h) J
   
3.         return arr
   6 y4 {6 N& @/ L
4. + d9 r* P! i5 |\" V- q\" P/ }
   
5.     # 将数组分成两个部分, k\" ~% |% v5 A2 d8 ^
   
6.     mid = len(arr) // 2) d1 G1 r! O! n8 {% q. w
   
7.     left_half = arr[:mid]
   8 {6 N. N0 U$ r# O5 J- S, t4 Y' d
8.     right_half = arr[mid:]
   5 i, S: q# Z4 Q# C* }# i/ C
9. 
   % |4 `+ Y) q# y/ n) V1 ~5 E) r
10.     # 对左右两部分分别递归调用归并排序
    0 B+ P\" F+ h' k, [) ~
11.     left_half = merge_sort(left_half)
    1 \( ?$ x5 x' ]( ?9 f
12.     right_half = merge_sort(right_half)8 \* P2 l$ N3 [
    
13. 
    # N0 y) r/ `9 ^* v- ~7 Z* s
14.     # 合并左右两部分2 B8 u6 |7 U9 r& G/ x& x
    
15.     return merge(left_half, right_half)\" F: l; H7 ~7 g( X) I2 b
    
16. 
    3 {9 x, z4 {$ N# V9 A
17. def merge(left_half, right_half):
    / F0 ^) z8 V* l1 w- m\" z' \4 h# Z
18.     i = j = 0
    7 W$ C8 @6 p6 Z
19.     merged = []
    * U5 D0 X5 s( ~0 E7 C
20. # S) h# d7 C; q\" g' t  g
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中. I0 A\" B3 U9 P7 g, w0 j
    
22.     while i < len(left_half) and j < len(right_half):/ Y$ Q( g+ K0 X$ p; u! s+ p9 @
    
23.         if left_half[i] < right_half[j]:  j\" Y9 D, r$ i$ D. d* F  a4 [
    
24.             merged.append(left_half[i])  g' C/ A( m8 v8 o
    
25.             i += 1
    5 E/ G  L, O) F6 a  g& z\" L0 |: |
26.         else:
    ! y; _4 I/ C+ @* }) L! ]6 {% h
27.             merged.append(right_half[j])# [3 a. A6 H- h' L2 g: |  f4 Q8 a
    
28.             j += 1
    0 w0 i9 D7 x# p. W- T$ S$ U. j
29. 
    7 V9 `( ?& W  b
30.     # 将左右两部分中剩余的元素添加到 merged 中
    ! R7 j- F\" ]\" }5 v! y7 r
31.     merged += left_half[i:]
    2 H# w# n; _( t9 Z& j
32.     merged += right_half[j:]3 c' H! b\" y- T  P9 T
    
33. 
    5 |% e7 D0 u6 D; A$ F3 M* W
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   2 [5 s3 Y: ?4 c+ \+ l6 I% w
2.     if len(arr) <= 1:' c7 V+ B6 R7 x\" L) X\" u\" R
   
3.         return arr' `5 K5 n: h' s. \
   
4. 
   & ?' b$ {$ Z! U# R
5.     # 将数组分成两个部分$ r' l1 i& \2 P) y$ Z, t  V( a
   
6.     mid = len(arr) // 2& b& W: R- N  v6 w4 n, C2 E
   
7.     left_half = arr[:mid]
   $ s& W& w6 z- E
8.     right_half = arr[mid:]
   * r; R6 |. Z3 {( u( t- X9 m
9. 
   : V. J$ D\" b' b4 }' A6 l0 B4 w
10.     # 对左右两部分分别递归调用归并排序
    ' C; R- U+ v8 p) y! R0 v8 @
11.     left_half = merge_sort(left_half)
    . b/ |) O# g0 |\" T  T- U2 w
12.     right_half = merge_sort(right_half)
    3 N4 s: G4 s& a  @$ d1 W' d# s! l
13. 
    + z6 D\" q, G2 i4 D
14.     # 合并左右两部分
    & j, _) P$ ]/ f
15.     return merge(left_half, right_half)
    ; \+ V2 }4 g7 ?5 ^
16. ```4 j( f( H\" @9 s9 v$ i* a! H2 i
    
17. 8 D% a2 `2 J/ k% t  @
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。9 A& o) P: r# Y! q( w9 K1 _
    

复制代码

merge() 函数

1. def merge(left_half, right_half):3 ?% j/ j2 k) L4 t! [# e9 r$ A% x\" F
   
2.     i = j = 0* V8 _& W\" O( V6 l
   
3.     merged = []
   1 v  c% ^  Q$ f8 \
4. 
   / r( }' F- |\" ^. M; @1 o' O
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   8 N\" W4 b) t6 j: @8 T3 d4 ]
6.     while i < len(left_half) and j < len(right_half):% T\" h3 K1 i$ ^# ?
   
7.         if left_half[i] < right_half[j]:. Z) d\" U6 {% V9 U/ M- p! m
   
8.             merged.append(left_half[i])
   + {8 l. Q; |/ U2 P4 w3 W7 ]
9.             i += 18 G. V  E8 X9 q6 H, I$ |: {$ I
   
10.         else:
    ( m\" \1 g7 j# c: H
11.             merged.append(right_half[j])' u; k3 ^5 e& c% A1 {9 J
    
12.             j += 12 z3 @# ]  I* k. p
    
13. 
    7 L3 c* u& `' _$ @
14.     # 将左右两部分中剩余的元素添加到 merged 中
    3 U- [. R4 b  A; o% h
15.     merged += left_half[i:]
    : V5 `$ \- {% P! p
16.     merged += right_half[j:]
    % d  Z3 Q2 ]  o: B+ K8 W
17. 
    6 @- N3 G. `0 P2 r$ i
18.     return merged6 x% u  N7 a# P! j9 i
    
19. ```
    $ P2 F& Z' M7 {% ?. ~0 H6 i! T: n6 M
20. 
    \" `  T1 _4 d' t/ [. L8 A
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
- C( Z4 N! L2 t
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

( f# Y4 c1 C' u# v, E% F% G2 ~合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
' E! D. G6 R$ ^+ V
测试
0 ]; v) K) |6 X$ w" {2 @在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]6 i5 V5 R' b& N/ D( a3 F
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {! e9 L* U+ f) X\" O
   
2.     public static void main(String[] args) {
   - x+ H# Z6 x$ x* S
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};\" S\" R! N2 k2 I
   
4.         mergeSort(arr, 0, arr.length - 1);
   5 w* C; r5 c8 S; L\" }& i' s* x2 M( {
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   8 G* l7 ~% j( c) Y9 b$ L
6.     }
   & b. W( B5 Q; r; e  m) F
7. ! E) B/ P; n/ c' ^/ d1 _$ a4 H% z) z
   
8.     public static void mergeSort(int[] arr, int left, int right) {4 M4 E$ E7 j5 w8 }* b' ?8 V
   
9.         if (left >= right) {\" r( Q5 \) L3 h& g2 F) }5 N( W
   
10.             return;
    , E; @6 V$ |) M# }5 T8 Z: _& s
11.         }
    3 H. H+ k, q5 w# e- A& X, D8 S
12. * H& O0 l4 F7 `8 _( F& ~
    
13.         int mid = (left + right) / 2;& \0 S- L/ _9 d% N
    
14.         mergeSort(arr, left, mid);
    / U$ p7 k3 x: U' e+ Q4 ^
15.         mergeSort(arr, mid + 1, right);
    & Y) f+ v4 M$ t! T1 W1 L+ C
16.         merge(arr, left, mid, right);8 s, `* f( H( a! Z- ~
    
17.     }
    7 p4 z+ d7 G1 B! ]! c
18. 9 k6 f  o2 a  n! i7 q
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    0 C9 ?- P( Z8 j
20.         int[] temp = new int[right - left + 1];
    2 d- b* [* f* z' H) B; j5 H
21.         int i = left, j = mid + 1, k = 0;/ c6 j: G5 w2 m
    
22. 
    $ ?8 n$ s2 Q  s; D, ]( m7 o
23.         while (i <= mid && j <= right) {) l( p, l+ S\" @3 {
    
24.             if (arr[i] < arr[j]) {
    \" g3 g; ~* ^  y. a) V
25.                 temp[k++] = arr[i++];
    \" ~* u* x8 \/ y: w/ {# V! G# e
26.             } else {
    3 X  ~\" N1 X4 Q. O
27.                 temp[k++] = arr[j++];. M$ t, [1 X* O( |% C% S
    
28.             }
    ! h& F5 H; m0 q: g- z. q+ a
29.         }
    6 t7 B8 m! N- q% y
30. 
    & B( N6 z/ n2 \) U
31.         while (i <= mid) {5 U) X6 c# P( ]\" I, u  j; {
    
32.             temp[k++] = arr[i++];
    9 }: I5 v$ y6 z$ w! G. c
33.         }# e. k, b& ^% E: U, Y\" x2 `
    
34. ) t6 j2 A% @7 q2 ?
    
35.         while (j <= right) {! v4 [\" T( Z! L1 z5 {0 ~; ~
    
36.             temp[k++] = arr[j++];
    5 E7 f. z% R5 }; c7 Y! U$ G1 K
37.         }# j: H/ G9 Y; K7 r# `' X' k
    
38. 
    : `. t* x2 ~2 Z% {9 {) T. j) J
39.         for (int m = 0; m < temp.length; m++) {
    ! ~' @3 r, W2 j- p$ I+ i# l8 y\" g* X% V
40.             arr[left + m] = temp[m];6 w# r3 C8 u+ K/ D- D4 ?
    
41.         }% x1 P# D+ X- m9 x; H: f( n
    
42.     }: t/ K  A3 f/ p  G
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {% ]1 v* k- s, p/ @# T' E% o# l' |
   
2.     if (left >= right) {, Q/ I\" S; c; J1 n\" F% U
   
3.         return;
   & A7 o3 L( _* y$ R
4.     }: O9 V7 [7 j/ r; _+ B
   
5. 
   ) ~( Q) R' L* Q- Y' u- U* c8 J% E
6.     int mid = (left + right) / 2;$ y. y5 p, U2 Z+ _
   
7.     mergeSort(arr, left, mid);$ z) S5 t4 e' R\" }& X\" P2 ~
   
8.     mergeSort(arr, mid + 1, right);! A3 @# _9 v5 S5 p' @
   
9.     merge(arr, left, mid, right);8 ^, E/ |. L4 l) a7 k
   
10. }
    # u+ l6 a  j' ?5 Y  n4 I\" ^; \, B
11. * V% @. r3 |% d4 `
    

复制代码

这个函数使用递归的方式对数组进行排序。
% s  F' ?0 G8 s8 A
5 l0 i- e3 k* Z' p/ S' w! C! [2 U对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
$ d$ k/ }. H, O8 Y7 l
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
6 ^4 c$ r, v# nmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {\" m( p9 N\" H9 ?9 l
   
2.     int[] temp = new int[right - left + 1];
   % y3 d% S% N$ W% c7 T; Q% @
3.     int i = left, j = mid + 1, k = 0;
   * z/ m3 g9 ~# a( Q& a
4. 8 l: F' v/ F8 Z7 ~' a
   
5.     while (i <= mid && j <= right) {' {' N. s9 N; Y7 h8 H' u
   
6.         if (arr[i] < arr[j]) {
   / t( Y\" l# V# u+ I\" y* o) V7 |
7.             temp[k++] = arr[i++];3 X( Q6 n% r  A4 {' o7 p* J# H
   
8.         } else {
   $ L6 H  [/ U) ]) D5 k
9.             temp[k++] = arr[j++];
   ; t/ T6 i9 Q( e- e, y( d
10.         }1 G) z* F7 R) t. j8 h
    
11.     }
    6 k/ w# i. H6 j6 ?. R. G: k1 V# [
12. 
    3 R7 L6 `. K. l2 F  M
13.     while (i <= mid) {# S6 V, C4 c* z+ N1 y
    
14.         temp[k++] = arr[i++];
    - R$ `& n* H5 x\" e
15.     }1 j( \* P  a7 g# g' |0 d3 L, j3 }
    
16. 
    : \- P( g+ y7 T. l. u$ M
17.     while (j <= right) {3 q2 Z1 O4 ?( D- i( Z5 J. v. I7 Z
    
18.         temp[k++] = arr[j++];
    $ s, O: ~9 A\" I( o9 [' r
19.     }3 V5 A8 e' J) L& ?6 A
    
20. 
    . K1 k7 d4 ?* t, n# I. d# G
21.     for (int m = 0; m < temp.length; m++) {
    / j7 w% n$ M5 W/ Q- m
22.         arr[left + m] = temp[m];
      L, I: X) ]9 Y0 s\" b
23.     }8 A$ V9 H' C2 }# |\" k
    
24. }
    # Y4 I- R4 s\" {, w\" r5 y

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
; D+ U; x* x+ R5 Z
9 i6 Q: ~3 Q( A, t' z% G' S9 V合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
# u4 _& b$ e0 L% t8 M3 C0 G2 c( B
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
' _$ D* g2 q+ W  \; `/ |: a
2 R# I2 N" j6 Y; V需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

# f/ p# u$ ]& j" s" f这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

7 F* h% k; p  b, x3 E! V6 ?
0 N! F) N- |% E: q. N/ B$ O4 s

" W* D$ g' o" u9 F3 c, {4 Q2 s& y7 P  s

2 w0 V5 _* q; F- l
+ w& A! ?' X3 K* Z3 v( i