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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
& u0 o4 _9 N/ R  v  W
6 I% _3 ~( }: X4 L8 w以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
) o) P; v( ]1 k( x2 K5 s
7 A  v$ X0 ]8 H. e2 F: M/ W/ T/ \/ L插入排序（Insertion Sort）

% _4 ^, l# l- {选择排序（Selection Sort）
, w( `8 S& m8 ]' A, p
& |: d1 B0 R4 q. o" B* N0 I0 X! u归并排序（Merge Sort）
* X- P9 Y2 D  k5 p! k) `8 i
; g  V  n. i4 r/ W1 ~快速排序（Quick Sort）

堆排序（Heap Sort）

2 {; V' n9 I6 p一、基本介绍介绍
1.1 原理介绍
5 d& y6 P+ u% S归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
7 G+ s' C  p" q9 m4 j: M, X
# m1 g7 _: I# U( v. [归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

# k- p. H6 F( t$ X  k3 K+ H9 f分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
  _6 U  G7 [' \# y6 @
& t8 w: S" r8 {; ^9 g合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

7 S! J, ?. |2 h, ]- M* a+ o合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

' g5 o  b4 v' [! n( T6 P5 O  {( I定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
1 ]7 R; M* J' A' a
4 f$ g* d2 M" x* u4 x& i0 B比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
3 [/ ?, \& P4 Z9 b9 Z: E% X& q' j" x
% E3 Q  f  m$ j: a( y6 R重复步骤 2，直到其中一个数组的元素全部放入 C 中。
( X8 t6 K0 |6 C/ Q6 D3 ?. }$ N
将另一个数组中剩余的元素放入 C 中。
# E+ a+ `  L. M" L
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

: a9 @3 O' s2 R- y/ z原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
5 D# s' _9 M0 S/ N' T7 C
- _0 U1 g  M' k1 Y假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

  B" M$ P5 m% |5 O( r) Q首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
. o" Z% E- e' U. W
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

$ x* q, H4 C+ ^4 v$ `$ R4 q1 X对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
/ |& N( e! D0 u# q& G: L- Y
* i$ z# X, d; Y8 E接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
* X3 a( U. W* B9 @% ?2 S6 Q
+ m. Q6 a; u  d6 f" S将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

. U6 d6 E( p9 o7 e- r4 `因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
+ Q: p# Z1 X  V
1.2 复杂度
, ~7 B# U+ P, j- P归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
; `- ], f$ f7 N: W+ z4 Q
这个复杂度可以通过分治的思想来解释。

1 W. X6 Y& O% V3 \首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
; a3 ^: _: y; I4 z, ?- `
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
1 z6 Q8 o$ w7 Y3 R2 Y2 k& [
. H! }5 d) E- j3 @归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
1 l& U0 N! H& [7 D. B
2 c: `+ b1 A( D5 b1 w这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

7 y! l( d' f# D1 K! Q) Y1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
) d( @, }, t  |
  G( v2 [7 o) y' t. {; s& v对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
* T3 k0 q5 B: [
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
. R) ^$ Y' Y" U) [0 P- o; n
. Y: }6 o6 U, D; \0 ?对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
1 Y1 B9 n1 B6 |/ r# e  E5 z$ l4 x% G) K# {
1 Z# Z' s: Y# _! q对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
8 q# q7 b/ a2 p* E) n& L' V2 }# C
( \# t$ e4 `4 @$ G! D/ @4 s, Y总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
6 i! z' e1 W" t0 L; {
二、代码实现
2.1 Python 实现
6 d7 n  D2 r1 q$ n5 o- B9 l以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   . M7 X4 K2 z/ g! n- f, |
2.     if len(arr) <= 1:' r, g, `8 L) y\" u
   
3.         return arr$ [/ d0 N0 u' }. s* G9 v
   
4. 
   + w4 P- ?& Z) _
5.     # 将数组分成两个部分
   9 G: I) n: }2 E4 d0 G8 ~
6.     mid = len(arr) // 2* w\" B4 P  T5 U  n2 ~
   
7.     left_half = arr[:mid]
   ! _- V/ ^6 v( z0 m2 g2 J
8.     right_half = arr[mid:]2 f& f8 `3 m' W; t+ f# u* b& U, E
   
9. / @+ l- t+ f: h4 `\" w
   
10.     # 对左右两部分分别递归调用归并排序
    3 V& v8 p  L7 u1 c4 k% Q
11.     left_half = merge_sort(left_half)- [\" J8 [\" H8 j- W9 F6 Z, c
    
12.     right_half = merge_sort(right_half), q7 F: {! I# v, X
    
13. 
    ) Z) K2 Q' ~# D: F# A$ ]
14.     # 合并左右两部分7 B# I\" u+ q- C/ q
    
15.     return merge(left_half, right_half)9 {4 P: h+ ^. h4 |! q( T
    
16. . j6 l) l0 m$ K7 y( m
    
17. def merge(left_half, right_half):$ ~: V: x. M$ r; y2 {9 t9 E
    
18.     i = j = 0
    ! U. n, L7 N% V& }, n: ^; ~
19.     merged = []
    5 U4 h8 t# j/ {: R. M
20. 
    + W0 o* U$ N5 z, V2 p. r
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中1 ~, a; A\" ^/ b
    
22.     while i < len(left_half) and j < len(right_half):
    ' a8 r2 e& }( o3 A7 o
23.         if left_half[i] < right_half[j]:- J# R! g8 A) W( N- j
    
24.             merged.append(left_half[i])( `- ~- d( d. m9 B4 w\" `+ _8 Q) x$ k( W
    
25.             i += 1- X4 T2 k2 N: I! z# \$ |) O9 B
    
26.         else:
      Z% K6 \2 k; A; R0 n! D
27.             merged.append(right_half[j])
    * Q$ R* ~% P; k; l9 b8 ~* ^7 Y
28.             j += 1
    1 s  @$ v) t' {
29. 
    * W% U) m& r8 Y- w
30.     # 将左右两部分中剩余的元素添加到 merged 中
    * G; g1 ^% x\" v4 K- X
31.     merged += left_half[i:]
    , _6 B3 ~$ ]  z0 K
32.     merged += right_half[j:]# p8 h0 u& L  w( D$ t' p
    
33. 
    ) @( O\" K6 [/ T3 c+ O( A
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):9 M+ P4 \( p2 M+ c) z: i
   
2.     if len(arr) <= 1:
   9 R7 v  L0 m$ }  t' h7 @4 }
3.         return arr
   ! V1 ?' K% D( t
4. * g0 C% {( @0 q8 \! ~. P- _1 }
   
5.     # 将数组分成两个部分4 D  ~; o+ w. f) ~\" o
   
6.     mid = len(arr) // 2% ]) g) E+ `) x- s) i
   
7.     left_half = arr[:mid]
   & p& y% A3 C7 L\" j7 S7 o9 A
8.     right_half = arr[mid:]\" g% y6 m- Q# ^* D; W) o5 V$ i
   
9. 
   . G' _9 h) Y% Y! T/ |& b7 M
10.     # 对左右两部分分别递归调用归并排序
      P+ {! t% h+ t
11.     left_half = merge_sort(left_half)
    5 |. c4 ?6 c! l& q4 a' q
12.     right_half = merge_sort(right_half)3 c5 q- n( Q2 A- r+ K' ?) k) ^6 G
    
13. 
    4 s5 [$ ^) n- _% T4 @
14.     # 合并左右两部分
    # q' u2 K; F& U, F( f
15.     return merge(left_half, right_half)$ u$ @4 m: l' H( G! Y% S0 s
    
16. ```
    & I3 H) r5 K- m/ P( S# P3 u
17. 
    ' l; R# L* T. k9 T2 S, m5 U- X
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。9 U' O6 H6 {3 U$ D
    

复制代码

merge() 函数

1. def merge(left_half, right_half):0 Q2 {3 n# D  o! Z7 ^8 H& L
   
2.     i = j = 0
   , F# W. U/ k# I( e  t( I6 F
3.     merged = []& K! x/ ?$ E. l. l
   
4. * ~* F) q/ u: k- R$ `0 M
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中: Q$ K6 j2 U4 Q3 |* _
   
6.     while i < len(left_half) and j < len(right_half):
   6 D* b! O( I$ ?4 H- J! X
7.         if left_half[i] < right_half[j]:0 X# a! t7 ~3 B+ A; c' }1 V- \
   
8.             merged.append(left_half[i])  v% b+ ^1 T) n9 o
   
9.             i += 1( x# }3 s5 u$ m/ M
   
10.         else:
    . l. ?5 L1 [/ w* e* d& `+ O+ h
11.             merged.append(right_half[j])6 h\" @/ P4 N8 n( w. b( F
    
12.             j += 1
    ) [7 c. J; \7 N; T2 Q: z% A5 i
13. 
    / w  }* H: L* X
14.     # 将左右两部分中剩余的元素添加到 merged 中0 m' ?( u6 C/ [7 U8 h. ?\" ^
    
15.     merged += left_half[i:]' P. R& o9 ?% P& J& }  r5 z  G
    
16.     merged += right_half[j:]
    % n4 F8 h+ d! Q5 F
17. 
    , n6 m* G6 y; O' W: N
18.     return merged
    1 P( s: z; p3 e2 k
19. ```9 ^' n0 ?& f) f) h0 F
    
20. 
    8 v1 Q; p) z) O+ F/ k
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
5 p  W" Z( [9 O3 x9 V; `( a
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

* H# }8 y3 Z: [& ]* v6 a对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
7 k' K1 J( w$ t* ~" U) ^
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
$ o3 \) H  L: ^7 W/ s  y
测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   - P# J9 f4 @/ {  D- K) h/ m( O
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {0 ]7 x8 E1 \% {. ~0 J( Y1 i
   
2.     public static void main(String[] args) {, t3 O9 T% o; |; y0 T/ Z
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   7 P5 O- w) E7 C  B+ x- @: X
4.         mergeSort(arr, 0, arr.length - 1);
   + D! j3 F2 H! Q/ o
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]4 ]' j8 h* H$ K\" J
   
6.     }2 T\" \/ W. o0 ~7 K
   
7. 
   $ v) V\" B  i* f. c7 k& L. x
8.     public static void mergeSort(int[] arr, int left, int right) {
   9 a* H, i( C5 N) ?1 Z% Y7 Z) b
9.         if (left >= right) {
   \" Y# l- I, A1 S5 n' X\" G8 B+ j5 ?
10.             return;  l2 J' D  K. X/ ?, @2 V
    
11.         }0 b\" Z! y\" Q9 I7 {( L  m\" f7 o
    
12. 
    9 @0 N, `: w  X: [4 ?3 o3 M4 Q8 d0 w
13.         int mid = (left + right) / 2;
    , y% g) c3 x+ l4 d
14.         mergeSort(arr, left, mid);0 x. F/ |\" D9 u3 H# {8 x
    
15.         mergeSort(arr, mid + 1, right);* `( q2 W% X3 P, X9 @+ f! [! I! D
    
16.         merge(arr, left, mid, right);
    7 B, z% ?7 U. _
17.     }
    $ |# j* w7 f' H# ~
18. 
    5 E4 ~' w# Q% K; B
19.     public static void merge(int[] arr, int left, int mid, int right) {
    ' Z# d# L& ?5 `
20.         int[] temp = new int[right - left + 1];
    ' L/ }. Y9 j) D# {7 ]' _
21.         int i = left, j = mid + 1, k = 0;
    * {& h  Z$ B  K! Z( r+ w# W7 w% @! u
22. 
    1 ]3 V  e6 t\" y7 ]4 }
23.         while (i <= mid && j <= right) {) G% U' P3 o\" D+ H% O- F
    
24.             if (arr[i] < arr[j]) {
    6 z4 C) [# g% e( h6 p7 _\" }
25.                 temp[k++] = arr[i++];: K2 ]- r8 r\" `# a\" N( ?
    
26.             } else {
    2 T0 O0 f2 B% x) P2 }
27.                 temp[k++] = arr[j++];
    ) {* u7 \( M( j; T7 w' M) x
28.             }$ p1 S! u) D4 M& m/ ]: d' q
    
29.         }' ^- h2 u9 y/ Y3 W& o! O7 t- n
    
30. 
      F7 Z1 ~9 j9 w0 T\" T
31.         while (i <= mid) {
    ' J+ w' x: v9 m7 `
32.             temp[k++] = arr[i++];
    4 Q+ z& L7 i+ q4 k
33.         }7 p  r5 u# y( K% I* y! e
    
34. , J$ k, i# [! F. ]  }3 c6 j$ U. w
    
35.         while (j <= right) {+ _- D: F3 \+ s+ D\" w
    
36.             temp[k++] = arr[j++];
    : x( o# N9 w* F$ K) C
37.         }
    1 r. m/ @+ w1 e. n3 N
38. 4 h$ n: a# N- i\" }
    
39.         for (int m = 0; m < temp.length; m++) {
    / i5 L4 g, i; G
40.             arr[left + m] = temp[m];
    : k/ R0 D\" Q4 i0 n. E4 G4 K
41.         }& w- b  _* T7 R3 b+ Q
    
42.     }
    7 e' |) }7 l- |  C/ a4 H4 u
43. }

复制代码

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

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

" v7 K0 H! Q) n2 J4 }& hmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   / a/ c% [# l3 T: a/ Z4 h
2.     if (left >= right) {1 t$ ^7 b( v$ J, |: S1 A+ m7 {) U
   
3.         return;6 _' w\" [8 Z( d. y+ \
   
4.     }) b\" g% {9 |8 \
   
5. 
   , W) i2 g7 w' e) h
6.     int mid = (left + right) / 2;
   % K6 [* O' u3 }, S- m+ y
7.     mergeSort(arr, left, mid);
   3 }& S. M) ?5 o- o# @
8.     mergeSort(arr, mid + 1, right);
   \" \- B# }$ V2 _- L3 C  a) r
9.     merge(arr, left, mid, right);
   ! @3 _: |, \\" h\" I' e# @* T
10. }7 ^5 u  ^6 d7 F
    
11. 
    5 K6 P; \7 M+ s! W

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
: b2 X. N% C* m" S% w. O
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {; S- n0 Z' l- }; Q0 N5 j
   
2.     int[] temp = new int[right - left + 1];' t\" B1 f: P\" ^
   
3.     int i = left, j = mid + 1, k = 0;8 H, V, ^1 N3 s5 K: p9 F  X
   
4. 
   4 ^5 I: `2 U$ h8 l
5.     while (i <= mid && j <= right) {% k' }- p1 Y1 i5 W) t8 m\" i
   
6.         if (arr[i] < arr[j]) {( X% S/ o1 }) j. N  N$ z' q3 w; z
   
7.             temp[k++] = arr[i++];7 D/ }: p7 c$ A  l3 P8 H
   
8.         } else {
   * D) ^2 ~6 c- Q% E, S' r# C
9.             temp[k++] = arr[j++];- ?% N0 @, ]5 z
   
10.         }. t0 X; J- h9 B. I. v) n
    
11.     }
      S$ f/ e0 T/ y
12. 1 Y- K0 l9 G- h; S  k
    
13.     while (i <= mid) {
    2 E# k3 F( e3 @% L& ?\" c
14.         temp[k++] = arr[i++];/ l* W6 B! K# c\" M1 F  O) e
    
15.     }$ `* J$ k+ L9 u+ g6 d  `$ Q
    
16. 4 p8 Y/ p& n, m- r* {
    
17.     while (j <= right) {\" }) X, G2 L$ V( }% N: u- v3 K: w
    
18.         temp[k++] = arr[j++];
    - p) [  p# |- O7 k, ^. e/ [' d' G
19.     }1 c7 g( O! Y( K, N\" o. f2 j7 v
    
20. 
    1 [9 Y3 I( O+ ?- `2 n2 @) w2 `, W
21.     for (int m = 0; m < temp.length; m++) {. ^$ b7 Q\" I+ o+ n7 y1 }
    
22.         arr[left + m] = temp[m];
    ! ?, e. [+ H) z$ ~  o8 q( [
23.     }\" U7 M& O3 `9 s! t5 b
    
24. }
      \$ T2 K5 g- B

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
. c7 S- }2 A7 h+ d/ {3 H
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
( m# ^8 v. G8 i3 D$ [3 J
需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

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

3 e6 B$ f  S- i' ^, }# g" h


8 S, T  `1 t/ R  p# t

/ Q' A0 n7 U. P/ i: C4 c, v; n# W: f