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

2744557306

1 基础介绍
: ?5 d# P! y. x排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

  R0 w; {8 u( `) p6 {- N以下是一些常见的排序算法：

" x8 I& l5 v* {1 g+ i冒泡排序（Bubble Sort）
; R' i/ d1 L* {3 |
插入排序（Insertion Sort）

6 R! c+ u# ?9 D4 J% [选择排序（Selection Sort）
) [! c" a6 }3 V
, }$ p  [$ ~( ^6 T( ^0 c  N归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）
+ u+ E4 ]# I8 o- R1 i' d
一、基本介绍介绍
! A3 x# j+ @5 R% T0 S1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
, p  v' A/ ]; _: |" ?
1 ^$ X4 l# H: {# U+ l: T; I分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
- e, v( G1 G7 t, I6 s
8 l# B9 E& I) Q# x4 _' F合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
+ |) B8 ^+ e, e  s2 e
7 b; l0 }5 l" S  I- g合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
$ l9 t$ p, x5 {
. {5 n' o; O& Z" Z1 e. }$ J) X. ~定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
" e/ w3 H' k. [- i9 h- y
" B. T) j. c; m5 M2 G, A% w比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
+ `" e2 H. c  \2 k8 z7 }
将另一个数组中剩余的元素放入 C 中。
  K/ V* f8 R, j9 t4 k( C- f# M
& H& {1 t. S$ i& x归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
  u- @1 l9 S- k
; l& ~& @7 j* t" Y; H+ ~$ u' v原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
2 o" h; y( y/ c" L. m6 D
& k2 e% @  {% Z- n5 D假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
$ }1 }2 A/ Z% o
( Z1 N2 a( g2 g1 t9 p对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
( ^' L+ P0 t" m/ V
% u) R& K+ m5 J! M接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
: F9 k. w$ R3 K( ]" }. R! k7 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]。
4 J. I' s( l3 H* ]- o0 S) {- b
. V. S8 V2 x( b% C; O% S. }! y因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
/ [/ W; a, `! L
4 a8 h8 @. P) ^. j1.2 复杂度
* t" S6 j" u; `$ R0 g3 X归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

' q7 D* e/ F2 x- p0 I这个复杂度可以通过分治的思想来解释。

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

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

- P' C8 c0 F; A! U  l" |' [/ s归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

! G' p- |2 g! R2 o7 T  D这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
/ _: K2 `4 O7 c# ^+ j8 v, v) Y( Y% p. {
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
7 z3 l, h% o2 p7 ^
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
8 \6 g5 z# {# h6 t+ z
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
6 s" _" E- I" J- r- j% X7 b( U4 {7 g
3 M$ T$ D6 B  M, n8 p对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
+ u* X" G' J6 O, f" }1 G
: G* e0 W/ [% J3 @% B& R% c8 B对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
; a! |0 N/ q8 v2 _+ I8 F
1 e$ t2 \* _, p总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
. s; N3 h7 }9 o. @6 _
二、代码实现
2.1 Python 实现
% s) J$ ?* \; k6 z以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   5 M: u9 N# S2 u6 |' M2 Y
2.     if len(arr) <= 1:4 P% d) i( E+ x9 {# O7 B# n1 |
   
3.         return arr7 ]1 |* m) q7 V. `3 \0 c  v
   
4. 5 Y4 G1 r# [, q5 V5 Z2 ?
   
5.     # 将数组分成两个部分( d- f, z! U7 T: f! u2 Y
   
6.     mid = len(arr) // 2& J+ Y/ L. o( M5 }2 R  ]
   
7.     left_half = arr[:mid]
   8 y/ A* a3 o' T+ Z( a# s% M
8.     right_half = arr[mid:]0 k' u4 `; d* W/ c3 Q) |
   
9. 9 y3 N+ d. S2 P8 v5 z/ A
   
10.     # 对左右两部分分别递归调用归并排序
    2 q( l; v/ B6 ]* P' I
11.     left_half = merge_sort(left_half)
    ; d, Y7 S( m% T8 l: N( o! y
12.     right_half = merge_sort(right_half)7 |. n0 z$ l/ k# A* ~& \  C; z5 |
    
13. 8 m9 Y% j( I0 y2 c/ s2 y
    
14.     # 合并左右两部分$ D4 ^( x8 ^4 l% o& w
    
15.     return merge(left_half, right_half)
    ( ?6 o& M' I6 I
16. ' l8 `: }0 l6 |# e
    
17. def merge(left_half, right_half):
    % T  l4 j. E: [; b) P2 n
18.     i = j = 07 y1 P5 t) y. I! f3 V
    
19.     merged = []
    - w- p; E% J/ L* Y7 p2 [
20. 7 k- N% G* }1 @7 ]: q( j
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    % ^2 n- I$ l/ C2 z! X
22.     while i < len(left_half) and j < len(right_half):
    . H' m* M6 s' F& a! q3 y\" N3 n
23.         if left_half[i] < right_half[j]:5 i9 d. @6 J4 ^$ v; Y5 W
    
24.             merged.append(left_half[i])+ e\" m2 J- Q7 A- W4 d1 ?: c
    
25.             i += 14 l: ]) l0 H5 |) P# J
    
26.         else:
    / K( _! c. T$ N\" Q# R) E) o
27.             merged.append(right_half[j]); r. t+ }\" C2 D5 t
    
28.             j += 1
    9 O6 o6 w$ D) |8 e4 ^\" W\" b2 y2 `
29. 6 I. Y) G7 g* ^, t3 `1 Q$ y! \
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    % V* \, j) c7 g  }
31.     merged += left_half[i:]! {& v+ V4 T. r6 E$ R/ B3 r
    
32.     merged += right_half[j:]0 H! q7 {9 j4 C7 A0 N( X/ ~' o
    
33. \" E0 v5 F  f8 ?: R# Z\" G7 ~+ y) q
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   ! f* s2 Y. }% l\" r5 X- I
2.     if len(arr) <= 1:2 Q& R' m0 b: V# Y8 o( s  I
   
3.         return arr# S4 u- D  W0 V; l9 e
   
4. ) A: n; ^* q' e6 {% y% L1 v7 g
   
5.     # 将数组分成两个部分$ V2 e- u1 L5 c0 S; |\" d
   
6.     mid = len(arr) // 2
   . O5 o- e6 v% C- e3 e
7.     left_half = arr[:mid]  Z( n4 z0 X- w/ U+ J& t6 |
   
8.     right_half = arr[mid:]
   , g* v5 G7 d& ]2 [6 r0 j
9. 7 Q, ~/ h0 h6 x3 t3 @; G
   
10.     # 对左右两部分分别递归调用归并排序
    ' H) R. `: F. K  Q( p# f\" S# ]
11.     left_half = merge_sort(left_half)
    - u* c: ]  @' u; I
12.     right_half = merge_sort(right_half)
    : W1 j2 \7 r' A2 Q& P, ?4 x! T
13. 
    ) j' ?+ u3 r! M  A* r+ h3 ?6 H
14.     # 合并左右两部分
    ( f' E! k2 w4 I- e% V# p2 F5 Y
15.     return merge(left_half, right_half)+ H& x+ c, u0 U; B( D
    
16. ```
    \" U8 P$ d% V4 F7 B\" I3 f
17. 
    9 v  b2 r% k; g7 h- k/ i
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。- v0 C+ f( B; f- \2 [: C
    

复制代码

merge() 函数

1. def merge(left_half, right_half):: t8 A8 p, ^1 @\" ~$ `: @& J
   
2.     i = j = 06 y' L+ b1 d* S0 e1 T\" b
   
3.     merged = []
   # b' G7 W+ P; B
4. 
   ! h1 e) H% {$ O
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   # R+ A9 T1 `3 j. S! I/ E& o
6.     while i < len(left_half) and j < len(right_half):
   9 i4 M: {9 H% n* t6 b  @
7.         if left_half[i] < right_half[j]:
   3 D- S/ d9 ^) ?$ ^- h' _- k
8.             merged.append(left_half[i])' l, w  m+ z# z; d$ r4 b
   
9.             i += 1* g  M4 S/ k9 ^( p
   
10.         else:( S5 p# c6 l( u% p) j9 c
    
11.             merged.append(right_half[j])# J; x  ]# S2 i0 c! s- K2 ]
    
12.             j += 1
    3 p' Q1 E/ P+ }' s3 G: a
13. 
    % [+ @. p& g; |2 C
14.     # 将左右两部分中剩余的元素添加到 merged 中
    : w2 S+ m4 _$ h/ f) G
15.     merged += left_half[i:]% M- a' k: y4 U/ m
    
16.     merged += right_half[j:]( R# e' j\" c' g' U7 z! H% S5 J5 c\" O4 C
    
17. $ c% M# R% e. P
    
18.     return merged. b! q1 H# Z- V4 T
    
19. ```
    ( b! w! N9 y6 k/ f% F: z
20. 4 V# w8 V/ t. n, _5 ?\" [( N\" y; B
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

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

6 @+ X; u5 J" h" y  V( ^' q将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
+ Y0 j( `8 n6 w# p
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
9 D3 t- `! K$ z9 [6 e
0 Q7 Z% ~  S: G! B3 E测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]! s\" T6 G( m; S# D
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

) m, Y3 L) k+ }9 e) a. O2 d+ ^总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {& B+ Q( w5 w% C+ h
   
2.     public static void main(String[] args) {\" \7 M! b: Y+ y$ h, N, {. u\" m  n
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};1 r. Y7 Z' r* t# m+ i. F
   
4.         mergeSort(arr, 0, arr.length - 1);
   7 |7 O% T5 I\" R5 y( G  ^1 I
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   0 [: p2 y% Q4 ~3 s$ a
6.     }! l$ |* l: u6 m
   
7. ) d- c7 q- p$ u  n, ?, Y3 Q/ K# u
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   - ?; \2 j1 a; X: o
9.         if (left >= right) {+ E& {( h/ k0 ^\" b
   
10.             return;1 F) `\" b6 p0 m+ Q0 u
    
11.         }# a\" c5 e& T0 B, l& K( ~
    
12. & O* h+ p4 {, c0 }8 C. d
    
13.         int mid = (left + right) / 2;
    6 c+ _6 e6 G# S\" e6 V
14.         mergeSort(arr, left, mid);
    7 h1 m: y2 v4 `0 l  B3 T
15.         mergeSort(arr, mid + 1, right);
    / _3 ?. ^5 }6 l0 M# Z0 c
16.         merge(arr, left, mid, right);  ]8 c2 ~( c/ B& K, d5 @& [$ t
    
17.     }+ G& O7 B6 N9 e3 Y) A
    
18. 
    8 k. `: f$ u  ^4 z: ]& D\" _: I
19.     public static void merge(int[] arr, int left, int mid, int right) {
    6 @7 K! g  T6 s+ n* D\" b5 K
20.         int[] temp = new int[right - left + 1];4 k: G0 z$ h8 r5 B* w) C
    
21.         int i = left, j = mid + 1, k = 0;
    ) B6 m4 N6 P& [2 a( [* d3 U; h! {
22. 
    ; K; w, E5 B! _) w0 S# Z6 ~' U
23.         while (i <= mid && j <= right) {
    % C. p$ R9 z. x1 t1 }  `6 }8 Q
24.             if (arr[i] < arr[j]) {  ?6 P, `1 a  o* j: s2 U
    
25.                 temp[k++] = arr[i++];
    ! m. j  ^/ B- e5 o' g: T: u3 s
26.             } else {
    2 [2 U! q2 \% B$ x5 d1 k
27.                 temp[k++] = arr[j++];5 \8 @\" M% i& z# b6 ]
    
28.             }: I! h; [* u4 Q5 S4 X$ M
    
29.         }, w# Z9 I  G2 J3 v9 i' X
    
30. + ?- P) A7 Y2 V/ T1 K
    
31.         while (i <= mid) {+ t' s+ M' |. K+ G
    
32.             temp[k++] = arr[i++];
    4 P, q7 l& O6 O8 Q\" Y1 ^( S
33.         }0 J9 i+ y4 _! G1 k3 ]
    
34. 
    + K. r4 t8 Z1 v* B4 v  L6 V
35.         while (j <= right) {
    - J# v2 ?# R! n- p7 R
36.             temp[k++] = arr[j++];; ~3 P$ e; v- k1 l
    
37.         }# m& h( B  G8 l- h
    
38. 
    6 q5 t/ o\" ^- h# M5 R& `
39.         for (int m = 0; m < temp.length; m++) {
    ) w& n2 z% Q\" `; I
40.             arr[left + m] = temp[m];
    4 A2 l( ~, v) N* Z1 u. ?
41.         }
    7 A' Y' U- q5 S- _
42.     }
    5 o4 i! @* r9 k' o$ x
43. }

复制代码

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

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

! P# B7 y8 Q0 P- fmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {& W8 L# Q( V5 ?! R; d  [$ s+ K  V
   
2.     if (left >= right) {. p& K! p  E2 w7 N+ s/ C\" k- E& p! h\" t
   
3.         return;
   - W1 L9 r/ ^9 |# H
4.     }! j! B( N/ @( z6 K
   
5. ( ?/ }: D. y+ G\" ~2 x& f
   
6.     int mid = (left + right) / 2;
   + p0 h9 I6 x  P' F
7.     mergeSort(arr, left, mid);4 t& p\" @2 V9 S# \- q, ~
   
8.     mergeSort(arr, mid + 1, right);' e+ b# J) u' K; c# y/ d, ]7 F3 {
   
9.     merge(arr, left, mid, right);
   ) M5 f: b, K4 J$ z+ r. J
10. }
    \" b, s, \7 f! G0 b, O4 k$ u, {
11. / @$ h+ M\" E# [+ e2 M0 P/ \) l
    

复制代码

这个函数使用递归的方式对数组进行排序。
  P; ]& v/ @5 @2 n# P( f
2 A, Q9 t8 Z6 ?- D  `对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {+ e\" G; p! ~6 b3 [0 I
   
2.     int[] temp = new int[right - left + 1];- s. \) S& ?: J# r$ k7 _- \& a0 u
   
3.     int i = left, j = mid + 1, k = 0;\" U( a) S0 ~' V5 ]
   
4. 
   ! d9 H0 ^1 }4 ]& G3 L- C
5.     while (i <= mid && j <= right) {. a2 W* n; E  ^' E
   
6.         if (arr[i] < arr[j]) {+ r) h; E) g. S8 D2 c
   
7.             temp[k++] = arr[i++];
   5 k( l. c2 M8 k
8.         } else {; Q: ^\" A5 c5 Q) E
   
9.             temp[k++] = arr[j++];
   - o; @, k5 O) o
10.         }
    0 }* r\" S! [$ S\" H7 l0 V
11.     }4 t: h0 G: u' x8 F  r. A
    
12. 7 r; A0 ]8 p$ k, a
    
13.     while (i <= mid) {
    / {& a5 }9 M% ~* {( U$ H( n
14.         temp[k++] = arr[i++];* U- E- }& {8 A
    
15.     }
    $ C+ u6 }2 n4 ?2 P
16. 
    ( ^- z+ ~% w% ^: K6 d. {! q
17.     while (j <= right) {
    \" ^+ r\" g- R5 ]5 B* D, I
18.         temp[k++] = arr[j++];
    $ E7 O% m, l: n. p
19.     }
    0 D\" N. O  F6 w7 v; I
20. \" C. M) B1 b& r& ?! p2 Y
    
21.     for (int m = 0; m < temp.length; m++) {
    8 h  v% j) @6 i# K2 M% j1 d. s
22.         arr[left + m] = temp[m];. ^& g( p; _  R\" ^0 O
    
23.     }
    ( W5 U5 d2 P& A3 G  B2 Y
24. }
    2 z\" C8 m5 j6 p- O3 L  v# V: |

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
# w0 V+ u: e4 j5 I. x" I, _
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
3 B, r; _- c( F  r: z
  e% \! }' v. z需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

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





1 ^( l: b; w* i$ q0 L