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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
: H( R7 Q1 p: n# L: ~5 h$ w
以下是一些常见的排序算法：
5 I+ o/ B' `) s! p6 }; @' w
$ I0 z5 a$ r) \* c- ~9 Y. i; M冒泡排序（Bubble Sort）
% S# M  X* I% p) }. k. L) H% B
( r0 s; x! e* P9 M  H1 Y) Q插入排序（Insertion Sort）

* }+ L( [( s1 Q选择排序（Selection Sort）
) b; v" q& c. a2 @1 f
# n. B) Z3 q0 ]: s$ @8 _归并排序（Merge Sort）

! Z' S5 ]" j! I& T/ Z6 [快速排序（Quick Sort）
# O* i! a, o7 t& ^; S9 t) g2 r( @
* k# }% Z# |3 @0 b% t  z堆排序（Heap Sort）
! S% X( F1 Z0 X# N
5 u5 |) E: g% `& u& S7 _5 O3 {$ R一、基本介绍介绍
1.1 原理介绍
: [% M* s1 ^: `1 m) K) m归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

) w# m& k/ C3 O; y; F归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
1 L* c  I- n; M! f' b# R
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
" Z$ o) ]! I/ K) t7 V% o- G
& J; j( `9 l1 h- y1 b合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

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

# c9 g+ d5 m! y: \/ j$ }/ p" h比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

; g8 i4 O6 Y/ V重复步骤 2，直到其中一个数组的元素全部放入 C 中。
9 \( r& o7 z& q% ~! e
将另一个数组中剩余的元素放入 C 中。
7 u& S/ ^$ l% z$ j
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
5 x7 [3 N0 K% g0 K0 l9 e
; [, q# w( L0 }6 a* F; o原理简单示例
6 g# D) J0 j5 y, w以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

. T7 h% i8 c& J$ X& }假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
: e/ g. L2 p$ {$ s
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

& V0 G* e  `2 ~8 q0 N& ]$ n+ m对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

( s8 }0 R+ J' O& b, o! w- ?) v接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
( T1 {6 {. o0 j8 E0 e7 m6 R
1 b4 x: @3 \/ O- n9 y将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
; M% U$ A. D5 H% B
: D/ {8 e4 X. }3 r因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

) S* G4 R8 P- |/ m% Q  H7 J, C1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

6 v! q6 B( l* ?- z! c6 f这个复杂度可以通过分治的思想来解释。

2 x' v9 N  [1 _( D* [首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
! U# u  {; k7 v3 ~; U7 J
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
: h* x) b# @( Y2 Z. C
& Q" E, V0 _: _1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
) A4 \, O& h0 e& e1 `1 j
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

7 _9 D* C+ W/ ]/ R( N: C对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
1 z' k- y# b( g& R
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
9 q4 G6 b  W/ n, G
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
6 V  v+ W$ L0 V3 z8 t2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):+ d% X' M- p7 L  g6 e1 ^
   
2.     if len(arr) <= 1:! y6 O3 }6 n# e  t
   
3.         return arr1 m3 y1 |6 V8 U; N# j5 R4 X5 D. t
   
4. ) J) M# @2 y6 ^  {* l4 V6 H+ p
   
5.     # 将数组分成两个部分4 Z0 i, q: u\" H: D# K+ |) l) e
   
6.     mid = len(arr) // 21 |8 _  g1 E: c( J$ U
   
7.     left_half = arr[:mid]7 ?) \; o5 [7 E\" t1 I
   
8.     right_half = arr[mid:]
   1 v\" J% z  W( V
9. / D9 G6 R5 E. q5 e; {6 T/ E% j
   
10.     # 对左右两部分分别递归调用归并排序
    0 q# V2 E1 Q/ o- r3 X  N
11.     left_half = merge_sort(left_half)  ~* ^  P2 i; P7 i, v! v
    
12.     right_half = merge_sort(right_half)
    / G6 S3 C  Q9 V5 z# A; ]. v
13. / z, [- e( H: X- q, N
    
14.     # 合并左右两部分& q& M1 m6 Q1 T\" h. [7 r% C$ [; r
    
15.     return merge(left_half, right_half)# y5 P! }1 N# x* f
    
16. / \/ l* w9 P: }& ]5 v
    
17. def merge(left_half, right_half):& R& O( J8 t\" H0 h/ K) i: p  z
    
18.     i = j = 0& |: K9 x/ r) @( C, s. s( t
    
19.     merged = []! K* b, }. D) {7 m
    
20. ! b. Q9 v  {2 \. z8 p: s
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中0 X7 I+ E- ?. R, c
    
22.     while i < len(left_half) and j < len(right_half):$ b/ @0 n9 P2 \9 ~0 C' m. s  {3 f
    
23.         if left_half[i] < right_half[j]:: \% ~8 S7 S! x+ j% R
    
24.             merged.append(left_half[i])/ N6 G  P. ?- z0 c$ [4 k9 }
    
25.             i += 1
    ) r5 J4 i1 u1 T3 \( ?
26.         else:
    \" z+ y6 Y6 C% ?: w' N1 ?
27.             merged.append(right_half[j])
    , V7 d& u2 b: ]- W( M3 \
28.             j += 1- E9 P# P% d; b! [. L5 O, L1 `
    
29. 
    $ c0 i' g6 Z/ c2 e& O
30.     # 将左右两部分中剩余的元素添加到 merged 中
    - e' e# O0 i7 T& w  x+ A9 ?
31.     merged += left_half[i:]. M$ x7 j2 a! m9 S/ x8 P7 j
    
32.     merged += right_half[j:]\" F2 |( V) q; X! N) d
    
33. ( @9 G. W( |: a
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   # N2 F- A- s- h# N\" F6 I$ V
2.     if len(arr) <= 1:
   % Z; H$ R4 `/ ^  k* F
3.         return arr* _/ e: h0 R. _, h
   
4. \" |2 \( b* R7 t5 t4 H. P7 D
   
5.     # 将数组分成两个部分7 p1 Q6 P, P& D& v4 d# @1 ^
   
6.     mid = len(arr) // 2
   6 v/ C1 d( M1 e% O9 K
7.     left_half = arr[:mid]
   % o* B8 l& F7 T* P' @( W
8.     right_half = arr[mid:]
   : f( _' ~, _: P( E
9. 
   9 [- m4 I# M9 {: u/ q
10.     # 对左右两部分分别递归调用归并排序
    5 R. s6 Q9 r) {  W# N) x% N4 A
11.     left_half = merge_sort(left_half)( J9 y' C* k8 R* L1 b5 B
    
12.     right_half = merge_sort(right_half)
    + ]9 x+ }8 A, l: B
13. 0 t7 i6 Z8 n4 L/ x
    
14.     # 合并左右两部分
    # i8 ~3 e! N+ O# O\" x
15.     return merge(left_half, right_half)0 F3 Q' Z\" m2 r2 U
    
16. ```2 x& L6 X1 @! B2 J: [  ?- s
    
17. $ U+ N* F6 e5 O. d' A. y0 y
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。$ h( Q# \7 E- h! D. M
    

复制代码

merge() 函数

1. def merge(left_half, right_half):$ t5 D\" k0 C0 P/ L0 ]
   
2.     i = j = 0
   5 r; j' k. ~( v# @! D
3.     merged = []+ G9 o, O# B2 y, Z; d1 z! G
   
4. \" X) {5 M( F1 z, Z% p
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中+ y* {0 a1 o5 z* j( i4 q
   
6.     while i < len(left_half) and j < len(right_half):' i( t% S+ Y; _- D
   
7.         if left_half[i] < right_half[j]:( }- Z) ]  v8 t( Q/ ~
   
8.             merged.append(left_half[i])
   - {& w7 G0 ^/ `4 ]8 k/ h+ U
9.             i += 19 E& e+ U3 G! Y; S3 U
   
10.         else:
    ) e& U4 c) u- s+ V
11.             merged.append(right_half[j])
    : |& s! g2 S7 Y. N; q
12.             j += 1
    3 d\" q7 F' v# u
13. 
    ! R/ u% ^. ]3 e/ _! [4 m5 {
14.     # 将左右两部分中剩余的元素添加到 merged 中
    , g, ^0 b; @/ F: S
15.     merged += left_half[i:]1 U2 {. N2 J. E5 W' C
    
16.     merged += right_half[j:]
    : Q; o; H' [5 t6 q0 u
17. . b& Y) E. \! V6 n, n
    
18.     return merged% D) _: R1 \; Z
    
19. ```, u. ?. h' {0 g: {: q
    
20. 
    3 B4 T1 A* m) b8 Q\" x
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
- R; v, r  H/ e7 _
* t' e4 `6 h, q$ K5 A判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

% P3 q- o* c; \# t' |2 f1 R将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

9 R8 `6 L7 L5 I对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

) N" Z7 b7 L2 T! p9 `合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
) d! A( l) p/ t3 }( r6 L! `
测试
+ B& Y3 [# z( {! x4 D2 j在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   - g& [* m: v4 a- }5 B
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
. d5 f, E& T3 P" w, I) n3 \
) Z$ g3 A: c" p+ K总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {! u0 d0 u. N0 S' q\" U* p! \( x
   
2.     public static void main(String[] args) {' w3 J. [+ Y5 e/ L) r! W% |
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   # n6 U( d  {# F: M! F# @' d5 `0 o
4.         mergeSort(arr, 0, arr.length - 1);  O6 k: c7 ^* |
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
     Z& g3 `2 J! ?1 R4 k0 g* }
6.     }
   0 y0 x% F& y; ^; R  e
7. / j$ R8 x) G; H! I( z
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   ' \3 Y1 T5 f9 E& p
9.         if (left >= right) {
   7 s6 f3 Q5 n) h5 L
10.             return;
    ( P' |8 s' n5 a) W7 g$ C
11.         }
    4 l4 D# O. P9 A% m6 j
12. + M: Y/ N; h' J& q% E+ p\" F
    
13.         int mid = (left + right) / 2;9 c9 r  D8 n6 k. R& _! M! i8 P9 L
    
14.         mergeSort(arr, left, mid);- \, m0 m3 o9 ]! s2 q\" m
    
15.         mergeSort(arr, mid + 1, right);
    * J; B& o% @8 r* h& ]
16.         merge(arr, left, mid, right);
    \" U( f1 o( ^( p  W* _; v' s: p! w
17.     }8 g2 K( h, Y0 A1 }, r* r/ F
    
18. 
    6 d- m2 J' W: u& L+ y: R
19.     public static void merge(int[] arr, int left, int mid, int right) {
    8 x/ t& L; i% Q9 P- V; d
20.         int[] temp = new int[right - left + 1];
    ' o& k\" a, \- Q  W( g8 o3 Q0 z
21.         int i = left, j = mid + 1, k = 0;) W  P/ u2 O) J
    
22. 
    2 B, R/ J; H: b1 j) ]2 q
23.         while (i <= mid && j <= right) {
    4 U5 {! e6 [# J2 d* _  b- p& j) d
24.             if (arr[i] < arr[j]) {
    1 }+ s& `5 w0 O4 }5 U% ^# z
25.                 temp[k++] = arr[i++];% ~1 J2 ^\" w5 u& }, {: t9 C\" T
    
26.             } else {
    * i; Q! ?7 K+ v9 ^/ a. n0 d
27.                 temp[k++] = arr[j++];+ ~; h) w+ W7 j. ]2 g' p
    
28.             }8 G; a2 z; R$ S) p/ |# T- n2 s# Y
    
29.         }+ j# j) u3 y! X6 }2 w+ F
    
30. % q+ B\" y2 e& E' C# t7 y( z
    
31.         while (i <= mid) {- _& u/ v. R+ V! z; u
    
32.             temp[k++] = arr[i++];
      M9 t, Y5 w4 |* w1 ]: K% m
33.         }
    ( w6 Q' W1 ~$ [
34. $ t2 W* B; U/ M& E4 o( c7 Y5 t$ q
    
35.         while (j <= right) {
    8 f3 ~5 b  x# }+ k; Y/ y5 H
36.             temp[k++] = arr[j++];
    ( x8 X4 N3 z+ t% d+ Z! t
37.         }3 T$ x6 W8 `\" n
    
38. - V; ~% s; V3 X% i7 O4 t) I
    
39.         for (int m = 0; m < temp.length; m++) {
    2 A2 t6 t\" ^7 G4 n! h) u
40.             arr[left + m] = temp[m];8 h1 E% g, d! B$ @  R
    
41.         }
    / g$ z3 X7 I1 a
42.     }: D% `( ]  N5 J
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   . z9 t) D; r7 G% U# D1 ^/ o3 j* z
2.     if (left >= right) {& Y% |/ S8 j( ^3 m\" {$ c+ R1 Q
   
3.         return;
   ) ]  M, K& _& `% N$ Y0 b
4.     }; f/ b5 N3 Y1 ?' K. o
   
5. - E) |& p7 \% {\" _4 |
   
6.     int mid = (left + right) / 2;
   5 E! [& T  f0 ^, x
7.     mergeSort(arr, left, mid);6 u0 }8 f8 G) T# e' m2 L- i5 \. g! C
   
8.     mergeSort(arr, mid + 1, right);$ E/ B; H8 h1 ?' E# m$ T
   
9.     merge(arr, left, mid, right);; N% D1 a5 J% K# X6 ~% O0 ?* U/ R
   
10. }$ j9 I3 r$ ]$ [( \' Y, R# N
    
11. 1 J- @) x/ a$ W
    

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {, }3 H1 P  {- a: s
   
2.     int[] temp = new int[right - left + 1];4 Z: V2 N9 o2 H* _+ b8 q
   
3.     int i = left, j = mid + 1, k = 0;
     j, ]: X: \0 L3 m/ A2 E
4. * a; v\" q( m3 y. K) v' Z; X7 V
   
5.     while (i <= mid && j <= right) {! t. ^! S2 ]( ^1 _5 u$ [
   
6.         if (arr[i] < arr[j]) {1 a6 L! `/ F. ]2 ?
   
7.             temp[k++] = arr[i++];' O* S6 K4 Z3 [+ d, I
   
8.         } else {1 F\" }\" c+ C0 v0 Q9 B! k
   
9.             temp[k++] = arr[j++];* g6 K: Z& L2 U, s) D\" h* R
   
10.         }2 T1 W9 f6 v( w% W- G
    
11.     }
    7 ?4 I2 d8 m. y) z0 B
12. 
    ' p/ Y1 R2 R/ P2 t\" V
13.     while (i <= mid) {
    ' `9 t3 U. L\" u3 Z4 t( ~8 |$ @' ]
14.         temp[k++] = arr[i++];
    ' P' \# P! R* [  F% T
15.     }. p* m7 B; j- I\" w( j2 e
    
16. 4 ^7 R' y$ y4 h! S6 r
    
17.     while (j <= right) {* [* C9 ]( e0 E% o2 J2 |6 w
    
18.         temp[k++] = arr[j++];8 D# X4 ]. H5 N4 w1 ?7 ^1 F7 P
    
19.     }' }6 @9 ~5 H! z
    
20. 
    * ]( c0 |( `0 u0 \# Q3 e6 u
21.     for (int m = 0; m < temp.length; m++) {, P9 Q2 ~! ]\" C9 Y+ W8 \( q7 f* R
    
22.         arr[left + m] = temp[m];
    + ?, R# _* l1 o% F( G
23.     }
    / {. B, U+ J6 S5 `( i5 V\" ?\" N
24. }9 _1 F* U$ H5 ]: T\" ?
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
; h/ B0 |6 O7 S( a9 E
( b5 U( d+ x% g& D* j' {- A合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

2 |  F& a# q1 _" x/ I* |5 w最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
: f: H: D/ ?1 x9 t7 ~- o
. _3 q) J0 v' d& r- g3 r9 S: [需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
% a3 H0 @4 ?+ h7 T! N; A
! W) U3 J8 @' P9 b* I这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。






: U4 [5 z  f0 r+ }