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

2744557306

1 基础介绍
6 P: P) o. }( K+ M4 [, k排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
" r1 J! X& p: i) k5 B! v( k9 i  c: E1 R
以下是一些常见的排序算法：
% Z" q* y6 }+ j# J
9 u* N, q: [" `; y6 m' H8 v冒泡排序（Bubble Sort）
. j; W% {0 j9 _4 t: k1 ]
% a6 f* o' o% p! T! d. ~插入排序（Insertion Sort）
4 W& {- w/ r# ^; L
选择排序（Selection Sort）

) g$ ]1 D' C3 X7 A/ p( y归并排序（Merge Sort）

快速排序（Quick Sort）
  d% f+ X: w0 A& V
+ j: \3 l, w0 I8 j8 {) `3 Y堆排序（Heap Sort）
1 ?4 K" J1 J. X0 A6 W, \
' V. U+ n  O. p2 p6 `$ U一、基本介绍介绍
; v  ]7 r1 Z. s8 Z9 }1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
3 \/ m0 q$ F9 B6 D
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
- }' q" D* @: S$ v) u) R
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

$ Z( w' I$ O. C0 y# n合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
# `5 Y) _# ?% b; X7 V
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
5 U2 p6 Z2 r% O4 H
/ G9 Z8 v2 G! q! V& {比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

% r' X9 H) @( N  X重复步骤 2，直到其中一个数组的元素全部放入 C 中。
8 v$ |4 U* G8 N+ E# g
& U3 q' g5 I  f8 ?. c# K! O: V" F将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
! o0 Y9 I( Z* w" G
7 U5 X7 p; m0 U  g: u' h原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

/ u- W0 ]3 y  F" o: s! V5 u5 M& J首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

$ j$ j2 `/ F: o对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
9 G5 Q, S( H* M8 _/ e# S1 L1 Z
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

, I' d" K$ [  [' g- A将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
6 s3 Y3 ~' C1 P, T3 `* E; X$ k: O' \
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
* a& z: q6 j2 n0 l, Y
' Q3 O2 f8 q. W9 [% x+ `1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
5 ?8 M, C4 z; _. j3 G' F
这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
' p# V7 H% K) X/ J7 P
' O' E& w& Q( t( K$ P每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
# _4 d" ~2 k7 Q0 I( F, V# c
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

% |2 M4 {0 d( y1 b. D这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
# X1 E( k  f( m0 y* r
* X- d) q  u5 D# Y/ k  o1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

1 [$ x' P+ K# P对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
& s3 o8 G4 D/ J9 X
* S2 _0 O( ]2 E) X  e4 L+ X5 c对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
) O& q  {5 y  q+ E' M. R2 y: d
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
+ q4 H: L- z7 n0 [% d' ~$ U3 B% j
7 a7 x, X) N! T* O二、代码实现
2.1 Python 实现
+ T3 |" t: a. _" g3 ~以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   - k* Z, w- w* D9 g( Y
2.     if len(arr) <= 1:
   5 Q& s2 P- O  {2 M1 g
3.         return arr
     N5 y- `0 I\" Q: L# r6 ]4 K
4. 7 \9 a+ H8 [1 U1 W6 r+ g% m, W! z
   
5.     # 将数组分成两个部分
   ( ?3 L( t6 l% ^8 n% [
6.     mid = len(arr) // 24 {0 _$ l7 v, T\" v  ?
   
7.     left_half = arr[:mid], S% D: D  J1 H6 f
   
8.     right_half = arr[mid:]/ F9 ?% K/ c* y& w
   
9. 
   & N0 s7 r\" [1 ~- L
10.     # 对左右两部分分别递归调用归并排序
    3 B! p% k) b3 p0 A4 l* D# g* v5 M
11.     left_half = merge_sort(left_half)
    , N\" ^% r. J; R/ G6 v
12.     right_half = merge_sort(right_half)
    + P3 U6 T9 M* O+ `
13. \" m+ E8 B\" l/ `0 \4 w3 D: T
    
14.     # 合并左右两部分
    6 W6 {2 l7 P! O3 Q( y
15.     return merge(left_half, right_half)
    2 b$ J4 _/ }4 G1 Y
16. 
    ) j; c4 k6 e: `2 R* v
17. def merge(left_half, right_half):
    5 l\" x3 V, x5 S! D; G
18.     i = j = 0+ `, u2 i+ e) N9 S6 R; S$ Y' I
    
19.     merged = []
    , |1 |\" n7 Q, A) H6 v
20. 4 Y/ I7 h& x) X5 o) H
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    / b1 j# R4 s. D1 `9 h- t2 O
22.     while i < len(left_half) and j < len(right_half):. Q% i\" f) l9 @
    
23.         if left_half[i] < right_half[j]:
    \" O\" W% {( r- ]2 n
24.             merged.append(left_half[i])
    * J+ f- }) R8 h\" i\" q. B; U
25.             i += 1
    9 K0 v5 _' d8 m9 @. N4 @
26.         else:% ?4 m2 x( V: k& @1 M1 w
    
27.             merged.append(right_half[j])
    / X* l. y& c4 v\" T2 H' ^  z8 P
28.             j += 1
    1 W: p- r4 R) ?6 z; x. G7 _
29. 
    - ^9 k+ C) k( }* r1 E: }
30.     # 将左右两部分中剩余的元素添加到 merged 中/ V1 C) |/ ^' R0 x
    
31.     merged += left_half[i:]
    0 Q5 o# q: L& f4 N9 y- w
32.     merged += right_half[j:]8 h7 x* |0 @8 |1 ~
    
33. . N8 [% C: N  k# P& T( f  u3 |
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   4 M6 Q0 k0 F/ A5 C
2.     if len(arr) <= 1:$ w  U7 s+ b- \% }( g# T$ J
   
3.         return arr
   ' ]) k% N, `' x& C; |5 f
4. 5 M' k6 @* v' X- S% {; L% ]( `, _& i
   
5.     # 将数组分成两个部分
   2 x- J+ {- t$ e. ^
6.     mid = len(arr) // 2
   6 g# v0 x8 v/ S# S; E6 @+ P
7.     left_half = arr[:mid]) y5 t5 m: w+ e7 Q! n$ M0 C# N
   
8.     right_half = arr[mid:]
   \" E+ V  }+ P( x6 W! B# ?+ I4 t
9. 
   + y2 W. Z3 q+ \0 E3 j5 P
10.     # 对左右两部分分别递归调用归并排序
    0 K8 H! y3 B3 w5 V  u( ?; O# ~
11.     left_half = merge_sort(left_half)5 g. M1 I# \\" O
    
12.     right_half = merge_sort(right_half)% `. b% m0 d* ~0 j
    
13. ' @% }1 b\" j3 o; \1 S
    
14.     # 合并左右两部分
    ) Y1 Y% D- B& h7 U5 ]
15.     return merge(left_half, right_half)  `: P\" c' {5 u- F6 c# W4 Z3 }
    
16. ```
    4 O7 E8 h0 q8 z\" `
17. 
    0 q0 O1 A; ^7 A! [
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。2 ]\" L' a2 C: l- B
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   ) y\" T' K. R: Z. V/ l1 B8 |
2.     i = j = 0% T6 t' |+ A) J\" o8 X\" d/ p- P/ @* f) m
   
3.     merged = []
   ' O/ @! j: u5 X
4. 
   9 C( c- ~' B4 ]# }- z6 j! \: S4 P
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   1 F5 s' o( R! a+ P9 q* q  N/ a4 r2 c
6.     while i < len(left_half) and j < len(right_half):
   + h& [% D+ ^9 N# {& l* O3 ]$ v
7.         if left_half[i] < right_half[j]:
   ' I/ y3 x- Z1 M, t
8.             merged.append(left_half[i])
   ; x1 j* F2 b: V$ s- u\" s
9.             i += 1
   + n; l, ^  \3 j: F$ }( D8 w# T
10.         else:5 Z. u8 n2 K/ b- N. ?
    
11.             merged.append(right_half[j])+ p' }$ Q. M# F, v2 G. x
    
12.             j += 18 ^4 s+ n\" q  M$ Q4 t: F
    
13. 1 s* q1 {+ Y$ P  H
    
14.     # 将左右两部分中剩余的元素添加到 merged 中
    # ?5 a\" o& E9 c+ ?: B9 e
15.     merged += left_half[i:], X4 l  h/ a7 C% I
    
16.     merged += right_half[j:]
    & b  T5 R; j7 u' V2 s/ R8 b' r
17. 
    7 v( ?+ e3 M; Y/ R7 E1 E
18.     return merged
    6 `- d8 w+ p7 I2 m3 b1 `
19. ```! J0 K4 [- v0 g& V\" u
    
20. 8 B2 }# z' X: Q9 _
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
0 k; t* n/ }- G5 s
: |4 W1 u& E1 L0 m( g, l将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

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

9 w- ?3 ^2 \. i; b; g& E合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
" D$ E, @/ v$ c) U# x
测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   ' l2 i; l' y$ ]\" c7 ?: O( b7 Q/ ^
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
6 E/ [% W1 w( U* z
; D( W: W' T- K总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
) Y/ u2 E6 ]' j0 S. K8 l; b$ z% Q2.2Java实现

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

1. public class MergeSort {
   3 l) z& F$ n2 s
2.     public static void main(String[] args) {/ F/ O0 \' n4 l8 N
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};1 M6 T! g, T+ F* K* S
   
4.         mergeSort(arr, 0, arr.length - 1);9 e+ i( A\" I; l& H1 U+ w
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   / C+ E- Y& J6 C2 g$ i
6.     }
   * i$ b1 Z7 O5 b' v, Q. H# i
7. 
   \" M  N. v4 x+ H* t/ x0 J! |
8.     public static void mergeSort(int[] arr, int left, int right) {( x9 \' q  E3 f5 N$ s
   
9.         if (left >= right) {
   % W! ?# I6 v( q, D1 D  U
10.             return;5 s\" D( P& J6 n5 P' ?4 D
    
11.         }
    4 C+ H  ]) y% z; @
12. % m; i' r3 R0 K' ?$ A& @
    
13.         int mid = (left + right) / 2;
    9 `\" l) O' j' r7 c% \
14.         mergeSort(arr, left, mid);
    , W. i; d9 u1 N# u
15.         mergeSort(arr, mid + 1, right);
    * E1 z$ t6 U9 |+ U2 K6 P/ F
16.         merge(arr, left, mid, right);1 Y! U4 A% G# Y$ a' U
    
17.     }1 e) |' u( d! L, I- o/ I
    
18. 6 J0 M7 s) k  ^! H
    
19.     public static void merge(int[] arr, int left, int mid, int right) {6 x7 h' g$ E6 J5 @
    
20.         int[] temp = new int[right - left + 1];  T. c\" Z% i# n, ]7 B! J
    
21.         int i = left, j = mid + 1, k = 0;5 a9 l2 Z3 F1 ?
    
22. 
    8 {) [# Q  u3 `: T6 ~. H\" K( N
23.         while (i <= mid && j <= right) {' x  u( C8 a/ z! k* n
    
24.             if (arr[i] < arr[j]) {
    & {# A$ W. B/ |! g' O2 E9 a
25.                 temp[k++] = arr[i++];; o+ f4 a& B( m
    
26.             } else {; l. m9 i/ W' i6 n2 |3 I* g
    
27.                 temp[k++] = arr[j++];5 M/ h$ y* G' B7 L/ `' L. i% R5 F/ L3 b
    
28.             }! [+ _& a( o8 Q3 R3 n  k
    
29.         }2 h1 d( F' S5 J' W0 J
    
30. 4 u* x\" N; s' ]- s
    
31.         while (i <= mid) {6 l6 i9 U% D\" n
    
32.             temp[k++] = arr[i++];) }: X: `- m0 M- ^9 U4 U- K
    
33.         }
    : z) E$ `9 z2 V4 ~8 L* w\" z) U/ a
34. 
    : _0 g8 S- `2 [5 ^5 L8 T9 H
35.         while (j <= right) {/ b8 k% q) Y1 P1 F+ ^. Z  M- b
    
36.             temp[k++] = arr[j++];
    2 q+ u$ ^! f/ c& K$ s' ?. L0 D- s
37.         }
    ' Q4 e5 k6 b2 R3 h, q  g
38. 
    ; q/ {, B& D8 u, L0 j! o
39.         for (int m = 0; m < temp.length; m++) {! F/ c+ x0 V9 E# c; o( [
    
40.             arr[left + m] = temp[m];8 p3 Y$ X0 U* l% ^\" M, l% A
    
41.         }1 ^, u4 u/ N  w0 ~' w* ?* @- z
    
42.     }+ o* [  u\" j5 ?. m2 t+ W; r) z
    
43. }

复制代码

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

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

, s1 Q& @  D4 [$ VmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {7 O+ r% G* ~2 c& x
   
2.     if (left >= right) {
   * I% v& b: k4 a; t3 h* `, [
3.         return;; E4 W8 @, {# L
   
4.     }8 N6 f6 s( s, {\" s$ z9 X7 q# F
   
5. * z. }: y# P- E8 T1 H( M) [
   
6.     int mid = (left + right) / 2;
   $ d8 F' }0 f+ l, H, W
7.     mergeSort(arr, left, mid);: b; Z3 ^3 ~' q) O
   
8.     mergeSort(arr, mid + 1, right);. A9 i, B* e  W\" h! ]
   
9.     merge(arr, left, mid, right);3 a. o. D6 _6 k
   
10. }
    ) \5 T. G) Z% @$ ~1 a+ e
11. $ S- Q6 `' _# Z) B: L6 z# G
    

复制代码

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

( J0 S/ _& {7 w" p  _9 w对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
, c+ ~. L' X$ o+ M# Q
9 g9 O5 I9 ^% }7 L最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {2 k: `+ A3 k% Z1 E! w
   
2.     int[] temp = new int[right - left + 1];
   9 g6 w, T; C: e4 w' W
3.     int i = left, j = mid + 1, k = 0;
   5 ^3 a' D' ?7 D
4. 
   & M$ y* K/ H2 s5 L, ]  ^! ^5 r
5.     while (i <= mid && j <= right) {& n# e' K. v9 E1 g  |2 L
   
6.         if (arr[i] < arr[j]) {7 G+ E7 H0 {; b6 F
   
7.             temp[k++] = arr[i++];/ g8 x3 P& ^, }! X
   
8.         } else {
   # K$ t* B( r. E1 @$ a: c
9.             temp[k++] = arr[j++];* H* q9 X4 b6 w. @  B9 V; d  d; }: ]( M
   
10.         }
    ( @% c* Q  D! X
11.     }
    - u) M8 ]. B) L2 U* U
12. 
    5 e' ~* T9 F: G# _7 M4 ^
13.     while (i <= mid) {; U' \' f. T0 c' ~' N
    
14.         temp[k++] = arr[i++];
    * _1 x5 z+ X0 w3 T5 I
15.     }- T\" \8 h! q! C8 x\" H  V
    
16. 
    3 G! N; J9 u5 E- }) ~. |2 {
17.     while (j <= right) {
    $ G# }% V9 Z0 r- U; X$ k
18.         temp[k++] = arr[j++];0 J8 @' p3 R7 q- N( `( E1 X
    
19.     }
    ; p( Z+ _3 g% o9 Z2 [
20. 
    2 {2 t; \& z( k% j8 R
21.     for (int m = 0; m < temp.length; m++) {
    8 L\" A8 o+ _! E, a* v9 L
22.         arr[left + m] = temp[m];
    \" z+ C! S3 U/ s# e- Y8 n$ X) [& A
23.     }
    3 n  D4 L, z5 A3 x
24. }
    + C2 @) |0 g3 x+ p, n9 y+ t

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

. {) M; m/ @) ]1 H  H4 v4 z3 t1 }最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
- q# E) q) x1 _
9 h0 I2 q. a" t需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
$ O' O+ y" }/ M$ l  s
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
3 h7 P* E$ K/ A$ T/ I1 ?




0 C! M0 W  A' B  A8 |. m( X
4 W" ]- x) c, t0 I- p% P" b