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

2744557306

1 基础介绍
6 l. e9 G$ f: D# R$ T- m# e排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
) |. {3 K5 h8 T+ Y7 ?& e7 b$ k1 W% Q
以下是一些常见的排序算法：

+ S1 U/ m6 c" l+ N+ p冒泡排序（Bubble Sort）
% f0 ]2 C) A; y$ a
5 ]6 Y) ~" m3 R3 M* y* Z插入排序（Insertion Sort）
% r) K' X* ?: n1 ?" h& t: j/ a! I
9 o% B# ~( N, n+ P8 A选择排序（Selection Sort）

归并排序（Merge Sort）

3 y, L& x# M7 X快速排序（Quick Sort）
% C8 U9 S/ \- W/ n7 [0 V+ R
堆排序（Heap Sort）

一、基本介绍介绍
! K' r" D3 H# ?. D7 J7 W  k% K8 t1.1 原理介绍
4 @  ?4 h' B, Z8 D4 K. E( i归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
& X+ h" t0 I& ?2 `4 D
0 H1 x0 W# m# R# a归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
" N( t+ J& [- ~9 s
! ?0 n% T9 Z# y3 G7 ~0 T' w; [5 v3 Z4 P合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
4 w' t* B4 @, s2 S7 }& v
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
- N& e0 S* b- t, q  D- Z
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
% Y/ Q5 {3 p8 v" O
2 U+ v9 g( j: ?比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
  j- E7 [$ V8 n, G
将另一个数组中剩余的元素放入 C 中。

/ k+ E$ e. \8 F# p7 M! ?& ^) h归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
# m2 S# a2 J2 V  o+ w( i
2 ^0 {1 Y! q* X& w! P7 e$ C原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
9 m+ e  i$ i/ f+ _) {
, O3 T8 U  ?8 o) T. I, d" L假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

& N- H; M: x; T首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
: t. |% P! u; g) e
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
5 x6 n6 s4 v) A
对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
- x7 u) Z6 N$ {
( c6 |5 d% `* W9 E/ G/ 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]。
8 z9 H1 W+ c2 |7 c! o9 m% n5 N
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

7 a. ~$ z: I! E* }& x6 m1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。
* j8 Q7 C4 G6 u5 `
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
, O2 o( a' L, C
4 i' N/ q9 x* b) i8 S每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
& l) i, b) @- L6 p+ z) ^. T
  A0 e5 n1 [+ x3 q' m8 X8 N这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
, _% D, x8 w4 M  a7 X0 m$ {
对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
6 G. j% b$ I. s$ B
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
% B1 W; K  v1 E( ]. k4 w$ Y% Q0 v
6 G' Q1 O' U8 D% [, T" j对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
( _- w4 y3 T) ~  O0 R
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
4 Z  D9 X& l9 q1 c1 u2.1 Python 实现
: A: s2 s- l9 }8 f+ @以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   9 C, x8 g3 L( m% F  |
2.     if len(arr) <= 1:! |8 e. x  g- X* F7 B
   
3.         return arr
   ; k; ]- S1 {0 I9 y' e
4. 
   ( a- U6 B4 X, i* [* p5 z1 y
5.     # 将数组分成两个部分
   8 O0 U\" ?! W+ m0 z' V& i- u/ N
6.     mid = len(arr) // 2
   , s\" Q. W6 p, g# y4 w\" B
7.     left_half = arr[:mid]
   + C! N. U( t' p- V
8.     right_half = arr[mid:]# N4 P% r\" B. ]. q6 V\" z$ B
   
9. 
   6 Y# l  ^0 @( v( g1 A- _
10.     # 对左右两部分分别递归调用归并排序
    * B: V) Q6 z- t
11.     left_half = merge_sort(left_half)  E6 q' @8 m, \* J0 l5 F& A
    
12.     right_half = merge_sort(right_half)+ P2 ~* K5 y4 u% @3 E% U, j( k
    
13. : F/ ~/ h  h  C- f5 `
    
14.     # 合并左右两部分
    . @8 [4 R. G2 ]% u
15.     return merge(left_half, right_half)
    6 P; Z7 ]\" y\" w2 S, d' i
16. , v2 s6 w* e; F
    
17. def merge(left_half, right_half):  n1 L5 [1 O' D: ?7 O9 I7 A% p
    
18.     i = j = 0  p$ M- s. `4 b* x2 E3 U6 a
    
19.     merged = []
    6 t) R% z/ y& l7 O  N
20.   E( O+ X7 H' o* J- f8 i- K8 y% u
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中1 \' k* d# N) f# Y% K6 J: w
    
22.     while i < len(left_half) and j < len(right_half):
    2 E/ E1 O  ]8 z3 e8 D
23.         if left_half[i] < right_half[j]:5 q% G5 w  v1 u& }' C. T# }& |
    
24.             merged.append(left_half[i])/ F+ @9 x) `$ J4 `3 I, r' J; X0 E
    
25.             i += 1, X4 o8 I. }( B
    
26.         else:
    6 }4 j1 l( Y0 |
27.             merged.append(right_half[j])0 B0 s: z6 N0 k, e! z* ]4 V& A
    
28.             j += 1& D/ E! D\" K& r  \- C9 d8 F0 M
    
29. ; I5 m( H) z/ t. ~2 W5 j
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    + Z$ `! |* t; `1 Z! {\" U5 T; n9 E\" z
31.     merged += left_half[i:]$ ~3 [. N; J+ z\" J, T
    
32.     merged += right_half[j:]\" n6 D% I8 n' {$ `
    
33. # U* F\" D: W: K& h
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):7 ?, z( ?4 i! H$ t1 L7 Q$ _
   
2.     if len(arr) <= 1:
   - t( @) S( Q- _' S' ~4 V) d
3.         return arr
   4 U) I& ]% C* E& \/ g$ p0 b
4. ! g5 ?0 m5 S4 d( o9 S0 `
   
5.     # 将数组分成两个部分  t% ]: V# W/ A) p) D2 t6 Y
   
6.     mid = len(arr) // 29 @) O0 ~% j\" |7 V% ~+ {  O. v3 P
   
7.     left_half = arr[:mid]
     q7 s6 j: u0 ^. |9 y
8.     right_half = arr[mid:]
   3 y, A- R6 D5 ^) S. ?
9. 
   / ?$ R! D7 X0 H* x
10.     # 对左右两部分分别递归调用归并排序
    $ e0 J. G7 A% M) E& g, i  W
11.     left_half = merge_sort(left_half)
    # N; W- _* f# A+ V2 I+ @6 V! @
12.     right_half = merge_sort(right_half), G, x( _! d  L* Q1 I
    
13. & f  H$ J  Y# z( I- p8 P
    
14.     # 合并左右两部分* M. b2 f3 j* V) I
    
15.     return merge(left_half, right_half)
    \" q! V* x# L+ |8 m
16. ```
    + a+ I7 L! e5 A* H
17. 
    / f/ e$ M6 C8 _3 ]5 _( N* @4 R
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。! W\" J8 j, c( `+ L4 U
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   ( S' G! @8 C- Q) y# ?& a& {
2.     i = j = 0
   5 S( m/ ~! ^3 Q4 Y
3.     merged = []
   1 Q* Q! [' U7 w- G3 h7 n* b) D+ E
4. 
   3 u. `( j  G\" A: W% y
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   2 i, K& b% `& U! `' k. ?
6.     while i < len(left_half) and j < len(right_half):% E# O+ y$ j; f6 L* f
   
7.         if left_half[i] < right_half[j]:5 f: s: p5 ~# ?0 s, V+ [! V
   
8.             merged.append(left_half[i])1 H: U1 V5 l% e$ l1 w: }+ y
   
9.             i += 1
     b! p  n' W7 @7 d0 J
10.         else:
    % J& c5 U$ M1 e5 I+ D8 |0 u$ `2 c9 ?
11.             merged.append(right_half[j])
    ) U9 v4 n2 ]) g8 O
12.             j += 1
    / |% ]6 n8 w/ O3 u
13. 
    2 i- [. A8 Y0 ], H
14.     # 将左右两部分中剩余的元素添加到 merged 中
    - A( E% [6 m; b- s! ?9 Z
15.     merged += left_half[i:]% _( J  ]2 J: F+ T, L3 [
    
16.     merged += right_half[j:]
    ! j- m' j& |3 Y: A2 Q
17. 
    ; D- B2 H1 T6 J$ F7 |0 K: M% P
18.     return merged
    . J7 \7 I( E$ \! i
19. ```
      ]+ ?, F, w' A7 l4 y! r0 F
20. , Y# ?9 r8 G8 F! X/ q! O5 f; N7 [
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
& R. c1 X& j# ]3 ~, n7 {  Z
( W$ ?* [# K8 f2 r: Q判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
  d# V; T9 D, A# X( ?
) F$ N9 V5 k) x( y将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
" b+ P( |. q7 z# v; \- k( D
( B& {: N1 T2 P对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

' M. d" }+ S4 E* H& }" u合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

. H! |2 E, t' D5 d2 ]! L: s7 q测试
2 [& W1 h4 m. ~/ \2 O6 N! ]7 Q9 e  j在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]) M/ q$ A  t! I- M6 }
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {
   7 P3 W! X$ K0 N# j
2.     public static void main(String[] args) {
   % e4 y. K7 i# W! K; }9 ?
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   # Q  I1 J! q( j7 C; Y2 ]0 d\" `
4.         mergeSort(arr, 0, arr.length - 1);
   7 Z/ T\" x. N, s5 p
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   $ ?0 i% L: v1 e* z! Z0 L
6.     }3 J\" Y8 T3 Q\" x  X/ k
   
7. 
   3 @; Z- Z; U% |: h3 o
8.     public static void mergeSort(int[] arr, int left, int right) {
   : i# v6 I( `: X( {
9.         if (left >= right) {
   / H5 W) i3 }, @- F
10.             return;\" x: f+ X! X/ T7 ~# F5 I
    
11.         }
    1 f3 q% H1 m! Z# R+ F
12. 5 A& q: c' z$ t- v6 }
    
13.         int mid = (left + right) / 2;
    ( _  ]' y3 Y2 Y0 M1 j
14.         mergeSort(arr, left, mid);( g2 C2 h- P5 K' |. H' X. e
    
15.         mergeSort(arr, mid + 1, right);
      Y+ @- m# U. W- L& f
16.         merge(arr, left, mid, right);( s2 Y& A9 p: W9 Y, ]6 ^8 a
    
17.     }$ t7 ~: W/ M# d) y! G) j) y
    
18. % Y! w7 X( d' T  V  {+ e
    
19.     public static void merge(int[] arr, int left, int mid, int right) {# Y7 P3 W- O9 l# l
    
20.         int[] temp = new int[right - left + 1];
    7 J* Q: [7 M7 a0 m6 ]8 r8 g& ]! y+ u
21.         int i = left, j = mid + 1, k = 0;
    1 _5 \3 A$ g* J
22. 
    ) O9 o5 Q$ M+ o* m' S
23.         while (i <= mid && j <= right) {& _/ w/ z5 L+ Y$ j
    
24.             if (arr[i] < arr[j]) {* A\" I: Z) `$ M8 N8 |$ P5 q
    
25.                 temp[k++] = arr[i++];9 \% h- Q3 O5 j  O. h) z/ Y& |. ?
    
26.             } else {& e5 I; m. J: N. t2 i
    
27.                 temp[k++] = arr[j++];
    \" r3 y$ n( I3 W7 m& w2 x# I$ |% p* j
28.             }
    4 R- q- q) N\" w- j2 d+ _
29.         }& W+ J/ T& o! ]; q2 n; J\" P- j
    
30. / O% `9 g& C2 J. B) x$ s) @/ x4 C
    
31.         while (i <= mid) {
    - e: R4 w# M& Z$ c9 j- ~5 l
32.             temp[k++] = arr[i++];+ ?3 |) f0 S0 f' `$ S; d
    
33.         }7 U, T# h- h  ]4 e
    
34. 
    - W0 D+ c% M' l9 D\" Q0 g- F0 I
35.         while (j <= right) {
    1 D' f# \7 s% W: ?
36.             temp[k++] = arr[j++];% g4 q2 k% {: K  s' G6 u; T2 D
    
37.         }
    # ?2 G8 Y+ Y! z- e
38. + `; r$ o8 t* V2 r7 d0 x* o
    
39.         for (int m = 0; m < temp.length; m++) {
    \" c( c, K* a+ `
40.             arr[left + m] = temp[m];/ C* s$ A. T9 Q
    
41.         }
    9 Y' z0 W0 u9 s& T
42.     }; y, Q) y6 [3 |/ n5 i, J
    
43. }

复制代码

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

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

& J% P3 ~- |9 y' w/ }mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {' ]0 u# F- a( A/ }' J
   
2.     if (left >= right) {
   : S$ z0 Q7 l3 ]' D* z\" A) ^
3.         return;  l; O$ W0 @# u% G- I) u\" U6 {
   
4.     }* C' v2 C# m; F6 O& N
   
5. 
   , T  {% G9 |0 t  |% |
6.     int mid = (left + right) / 2;
   . k! r' }% a! z1 y/ V; ]3 G6 c
7.     mergeSort(arr, left, mid);
   + s\" z4 D: ^3 L4 e
8.     mergeSort(arr, mid + 1, right);- o5 v, p. |4 J, S
   
9.     merge(arr, left, mid, right);
   : H2 {. R& Q& Y4 p\" n$ f
10. }
    , l+ a; w2 z/ y! e6 |8 \9 }
11. 3 a5 F  |: k# k
    

复制代码

这个函数使用递归的方式对数组进行排序。
) U4 z( ]5 ~: L" b
+ ?4 ]6 K* ?8 N* K$ Q" `* `对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
5 z( q- J; n# D/ [! ~
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {% a. w, t. t& Q
   
2.     int[] temp = new int[right - left + 1];
   0 `0 V- N4 B& D  x
3.     int i = left, j = mid + 1, k = 0;
   3 V, i7 @/ N3 ?0 q- o. a
4. 
   4 [+ A6 d9 o! J' R' e! x3 x: F
5.     while (i <= mid && j <= right) {
   \" B6 a# V* J, ]/ I+ s
6.         if (arr[i] < arr[j]) {  O4 ]( P  D3 {1 W\" A
   
7.             temp[k++] = arr[i++];2 |9 w$ T- I. k5 I' S' s
   
8.         } else {
   ) _/ F. E7 o* M  i$ u\" v  Y
9.             temp[k++] = arr[j++];
   ; b8 X/ E9 d6 w
10.         }3 M# ?) Y6 H: r0 E5 Y
    
11.     }
    * v% P: A+ A; Z
12. % n( G. U% G: T3 [7 Q# k8 v0 q
    
13.     while (i <= mid) {9 v5 ?1 w8 h; [. |
    
14.         temp[k++] = arr[i++];8 }. g\" a1 N3 W
    
15.     }
    , a/ E* w  Q\" H( {
16. 
    / C6 C: u% k1 s$ R
17.     while (j <= right) {2 `5 U' M) A3 q( u4 v# Y\" A0 l
    
18.         temp[k++] = arr[j++];
    & |: D  c2 c& k\" u) p
19.     }
    3 P/ S0 E) D( c, z' u' @, z& z1 l
20.   ^9 K, Q: P' k; _: K, U
    
21.     for (int m = 0; m < temp.length; m++) {! r  R! u. S% n- ^4 q5 A
    
22.         arr[left + m] = temp[m];
    ( l8 L% q, j6 ~. P) \6 H/ U1 g- ]
23.     }8 ?7 X: ^9 P5 Y4 J, {& o
    
24. }4 q/ ]$ t1 I, G' V1 s\" q: y& o
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
- v0 n0 }5 }6 b- b# V
4 H+ `7 E0 T4 o+ M5 T0 V合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
. j. r" H" [( ]! ~3 m, }( v
5 L! A3 H; l8 G最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
8 B, C1 |0 _, X, U, _
9 Y( S$ I9 q0 N; i9 B1 y需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

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

& \6 H% ^' _8 Q/ ^( a8 ^( C) m7 p
, @; |) }1 q* S) v* n

7 t. ]' x/ V. P( n
3 a# h' _! W* X' ]1 x* h