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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
' M+ V7 o, K, O- Z8 D8 w
1 l/ ~; H* i% z' l+ D3 M以下是一些常见的排序算法：
' |3 V8 z9 l- l. V
* N3 ^1 M6 L. D% C: g. X冒泡排序（Bubble Sort）
6 I6 \( ~* K& _) N( k
插入排序（Insertion Sort）

2 }1 o" W5 F) E- u+ c, a$ D选择排序（Selection Sort）
& a- ^% o# c4 Z$ x3 }7 y
3 v  J* \9 K) ?) B归并排序（Merge Sort）

1 j$ ?, }% C7 k  }! D) s1 j快速排序（Quick Sort）
; F) W2 o& n% g: I
4 W8 v9 d7 k% t" X1 D$ L# i堆排序（Heap Sort）

一、基本介绍介绍
& D( o2 y# U* q& O' u8 r1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
7 E5 [" x) D3 N2 l; x  E
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

3 t* h$ U# M3 _! x0 J分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
5 x7 j: y- \6 V  U; R# ?
3 w' ?" N- M% r$ ]+ Q( D合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
% c) m$ ^5 B- a+ g/ z3 d
" t* b+ m% H% `, G; |5 H0 t' e比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。

. x6 Z% f6 Q% e. g$ S5 p将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
/ R# J4 s5 V, x3 Q( r
! D& ^5 H* K) C原理简单示例
, I& l$ g. }, D! b* g* K以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
# a4 x: P2 h% g' J& k( i! X
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

# k  I4 j, T# h. W$ i& H* ^  e对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
5 p! Y6 t  G" S* ^$ l' o
将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
% L7 k3 {- `; v2 h5 E. U0 J7 p
4 B$ y; o" t$ d* l0 H4 ~- e1.2 复杂度
# z' Z  ^4 m& O归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。
$ K- H$ C( G8 @: ^
$ ~) Z, s( m$ }. n2 P. I: R首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
* O" w3 D3 T) Q4 N: P
% W7 G+ v8 ]. x1 g" |* R. T每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
! ?6 {+ Z; }0 Z
/ B1 j0 I6 f9 l这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

5 v$ H: t, G5 Z' y/ u7 }0 U3 e1.3使用场景
% J. [: i5 f* Z, j, |  t归并排序的应用场景比较广泛，主要适用于以下几种情况：
( M6 N: W3 X- T% k
1 B8 T1 [9 l, Z) c2 ?对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
) l% U) H! h6 c1 ]5 a' ~
+ |. c; X* B0 \4 Q: i, a# K对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
$ W* u) e9 h  q9 d0 s$ }) F
0 i2 H8 ]9 v# Y0 a% w对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
8 F1 ]# ^0 m! Y) M5 _3 u9 g
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
0 q! _# f! ]6 x6 D
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
2 W7 A. `+ s. w% C* ]% C: e# `2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   3 H/ t6 {/ ~+ O: V
2.     if len(arr) <= 1:
   : F5 u2 Y) H6 L
3.         return arr: ?4 e0 i- H( L( F3 i5 F7 y( `
   
4. ; P/ _: w, s5 o% V8 [9 L
   
5.     # 将数组分成两个部分* l# t2 o$ \1 `% d\" s; l% l6 H
   
6.     mid = len(arr) // 2
   & k0 G1 g* O% f8 O
7.     left_half = arr[:mid]
   ( \( N3 R; ^6 |( B- E) O
8.     right_half = arr[mid:]* e7 ~% w; u  o5 Z4 ^& e& v
   
9. 
   & ~6 B8 b- F0 g; X' h$ i  i. `5 ]& N
10.     # 对左右两部分分别递归调用归并排序
    ' F( I8 y; L+ P5 f
11.     left_half = merge_sort(left_half)
    9 F0 r2 L& V& r. W) k5 R6 W& ]
12.     right_half = merge_sort(right_half); J( t. M6 Z\" r2 ?: |# S; L\" M
    
13. \" ~1 W# |* f- @# W' S! l
    
14.     # 合并左右两部分2 P: ^0 r+ N\" \+ X/ }9 `
    
15.     return merge(left_half, right_half)2 M# P. E# p% B9 v
    
16. \" @' z% f9 J$ ~6 Z
    
17. def merge(left_half, right_half):$ i; ^6 T0 j* S8 G
    
18.     i = j = 0. F  b  [6 @2 I& x: L
    
19.     merged = []6 p8 q: g& D' p7 F% g\" u% v( r7 Z
    
20. 
    2 T, E4 Q( s# r9 ~) ]
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中# c\" n/ i( }- J+ c9 q8 f6 K) }6 M
    
22.     while i < len(left_half) and j < len(right_half):9 X3 w. {# _5 F  Q' t
    
23.         if left_half[i] < right_half[j]:* X1 B/ @$ O7 m* K4 E7 k# Z
    
24.             merged.append(left_half[i])7 H0 Y3 r\" g  G\" c3 G
    
25.             i += 1& I1 ?7 V$ G$ m& S. o
    
26.         else:
    \" [$ S9 P  Y0 R/ ^2 |* \
27.             merged.append(right_half[j])$ m1 g& T+ w/ |) {. d$ b
    
28.             j += 1' c4 K4 [6 a% I% l% v: U
    
29. 6 V; X4 v/ I, D1 q\" j! q3 Y$ ^) u
    
30.     # 将左右两部分中剩余的元素添加到 merged 中7 t* R  ^  b\" R# e$ L) q
    
31.     merged += left_half[i:]
    $ _+ G+ ?7 V8 W) s$ H, {
32.     merged += right_half[j:]
    * K- R' i2 K; W* Y
33. # A0 ~3 M1 K/ X, V9 M
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):) m5 l8 v% z/ A
   
2.     if len(arr) <= 1:
   * ?7 n* _$ J* P; ^1 n4 R# k
3.         return arr
   6 o$ [, F- e* M, y
4. 
   / ]% `6 ^# A) X1 t1 A
5.     # 将数组分成两个部分
   + R$ {6 k. e1 B\" Y8 i; _; D! X
6.     mid = len(arr) // 2- n4 v8 h3 N( E& j, X1 z
   
7.     left_half = arr[:mid]0 s7 W9 A& f3 g7 o8 A
   
8.     right_half = arr[mid:]
   / \+ h5 R: m+ L+ D) L+ ?( m
9. ( r# t\" k5 O( A0 W6 G4 R
   
10.     # 对左右两部分分别递归调用归并排序- H7 k8 |3 C+ c
    
11.     left_half = merge_sort(left_half), \) Y3 [2 U3 g+ s6 ]/ F1 @
    
12.     right_half = merge_sort(right_half)2 s- T+ ~3 G) u: H\" B
    
13. + K- K! S\" e  [$ {( o2 |
    
14.     # 合并左右两部分3 ?4 c5 R2 i$ d4 c
    
15.     return merge(left_half, right_half)- O8 y' E# R+ T
    
16. ```3 q! _! B. A/ @  \+ T& ?: y
    
17. 
    , M, L. l# t2 j2 z  ~
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。% O4 V) Y$ W\" X+ ]
    

复制代码

merge() 函数

1. def merge(left_half, right_half):% J* l/ R* M# c3 @
   
2.     i = j = 0- u: i7 V; l1 B
   
3.     merged = []  @8 U* \0 G2 a4 A& c
   
4. 
   5 N) L. ]8 M% @- y
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中) L; y7 B& T' C# h3 n/ F
   
6.     while i < len(left_half) and j < len(right_half):% _: [( b( o# D  l' F
   
7.         if left_half[i] < right_half[j]:# }! M2 D0 I\" {8 y. d
   
8.             merged.append(left_half[i])
   ! w' l0 g4 y- k2 E8 b! j. x
9.             i += 1
   & n+ y$ o/ N6 J# g7 L
10.         else:
    # U* d% U# R\" Y% R
11.             merged.append(right_half[j])1 f2 o1 i. d) W- _+ R6 \: @- l
    
12.             j += 1
    , G0 x& [( Y, ~. K/ d- B\" q
13. ) t# e8 u6 \' ^/ K
    
14.     # 将左右两部分中剩余的元素添加到 merged 中% T2 }  S0 w% K
    
15.     merged += left_half[i:]
    7 u3 t4 O  X8 H/ C  {
16.     merged += right_half[j:]
    $ q9 f! U4 K* T$ i% u+ o
17. 
    2 I2 n+ Z1 J% N, [7 G
18.     return merged3 @\" p# X* \8 ?: t# \0 i
    
19. ```
    - x. t8 ^9 m\" A
20. 
    & {: `& b6 m& E
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
3 |: r  X* M) J( P5 w
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
6 ^- d" J  S9 G- F5 H# y- o
) e8 K# b, L" A  M: I7 q7 _& \( u$ ~7 [将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

% v1 }% j6 B4 L7 o对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
  `+ ]( ]) Z; ^2 ]# K
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
2 z: a$ |% T. t, _9 E! j( w
# Z# D  L: Y* [+ n- v. I测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]: j3 N/ r1 ^0 }) e3 }% D
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
8 D# g0 _  i2 W+ ^; \, F2.2Java实现

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

1. public class MergeSort {
   ( h; p1 d/ m' `* T* A\" l
2.     public static void main(String[] args) {
   7 }( U. h) s0 j; S( P$ z! l
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   , w! n1 k+ U4 x7 y) y) |2 ?7 k6 S) s7 i
4.         mergeSort(arr, 0, arr.length - 1);
   6 Z& `* v- F; p\" j6 \
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]8 s  @( {2 {+ g8 K\" a7 k
   
6.     }; \' t9 ]( h7 C\" ?
   
7. 8 B1 _; C: o; E. A7 i; S; V+ k
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   + A( z5 j1 R1 ?2 X' B: k\" f( O
9.         if (left >= right) {
   1 ?$ z. t0 s\" k& D) Z
10.             return;. D3 ^7 T; p8 X4 s- I+ V; `3 B
    
11.         }
    ) B) d\" F2 _0 J3 a! ?
12. * `0 \( ~4 m4 [' E3 B* E
    
13.         int mid = (left + right) / 2;# S+ h) U- o1 n+ U: P
    
14.         mergeSort(arr, left, mid);
    ) S, ~: N' Z. x+ a\" ]2 l+ \. M\" G# G
15.         mergeSort(arr, mid + 1, right);
    . r/ U0 l\" ^+ |0 ]. J2 ?
16.         merge(arr, left, mid, right);: {3 X3 r! ~* p5 y; I
    
17.     }
    \" d  N. E& ?1 R& z
18. 
    7 o0 }; K; ]. M9 P, X
19.     public static void merge(int[] arr, int left, int mid, int right) {
      e8 x9 w  w. K. P5 |4 k( k* ]# o
20.         int[] temp = new int[right - left + 1];
    4 l9 {- L\" u4 G+ x
21.         int i = left, j = mid + 1, k = 0;
    - C. R) D* {; ^8 t( }, s; V# }
22. 
    2 B\" H, S/ W0 h/ J5 O; f, m
23.         while (i <= mid && j <= right) {
    4 P7 h* t! u, C/ N; R% K
24.             if (arr[i] < arr[j]) {
    0 Q0 k% s+ e- P0 v0 ~- x( L
25.                 temp[k++] = arr[i++];6 p5 P+ l: Z, P
    
26.             } else {
    * H& R. q( J, z+ G& V6 m
27.                 temp[k++] = arr[j++];
    ; Y- Q) d\" w' ?9 ?# v
28.             }- b0 E$ x- Y4 ~
    
29.         }! K, H) |) ?) \2 |& S4 J; d* D1 R
    
30. 
    ( l, ?\" c8 u  }\" Y* E% L# v
31.         while (i <= mid) {2 N! n. r; J' @) T3 E
    
32.             temp[k++] = arr[i++];
    : W9 }5 E$ ^4 Y4 X
33.         }
    & k( P- A# }( C) w* `
34. 
    $ p: ^7 w8 b7 a( d$ D
35.         while (j <= right) {7 ^# y- F1 E4 _2 r# {2 i
    
36.             temp[k++] = arr[j++];9 [1 [$ E5 |3 q\" x1 Y) F3 y7 h
    
37.         }
    ( P$ \* ?9 T2 ^: E$ A! L
38. 
    3 J  ], p8 N, X6 V- L$ h
39.         for (int m = 0; m < temp.length; m++) {
    ! e& F2 M7 b* R' B
40.             arr[left + m] = temp[m];* J7 g* u6 c5 v, |2 @' }% E
    
41.         }
    ; Z( n% j% x: Y
42.     }+ r4 M$ m; w. z' I7 j) K: S: ~
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   - l/ x; j# l$ D/ E
2.     if (left >= right) {5 I; l: N' a' F( j# l\" X( N8 [
   
3.         return;% J! |5 l2 m1 O, i7 @$ ?5 g
   
4.     }
   4 @+ ~1 D1 j# ]8 [\" E! D& c+ q& {: e
5. - m& M0 U& y- _) x
   
6.     int mid = (left + right) / 2;& i7 Z. o9 p0 K$ B' a& x* `
   
7.     mergeSort(arr, left, mid);: T: ]' X: x% J7 ~
   
8.     mergeSort(arr, mid + 1, right);
   # \, m  a) |) }\" a/ h
9.     merge(arr, left, mid, right);; a0 b8 T3 W- E# C1 p+ j6 ?& p1 }7 M
   
10. }
    7 `. h0 _$ p7 r: _9 l) k
11. 
      n# K7 R+ M8 @( I) D* q

复制代码

这个函数使用递归的方式对数组进行排序。
  W9 D4 p- f3 t( @& a0 g+ M5 t
0 @: n& Y( w( X- K8 X对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {/ a  ?* D% E3 M% G8 C, L* r. `9 [
   
2.     int[] temp = new int[right - left + 1];
   $ d: t( L5 h/ [$ ^/ Q4 y, O7 j
3.     int i = left, j = mid + 1, k = 0;
   # ?( a/ v# w+ K2 Y7 c1 j6 P
4. 
   4 E7 O6 d% `) F\" H; f! U- x
5.     while (i <= mid && j <= right) {
   7 ?+ {: K8 R. s8 r5 f+ L( y
6.         if (arr[i] < arr[j]) {% ~) O+ ^- M% |5 S4 j0 N
   
7.             temp[k++] = arr[i++];
     v: u$ Z0 M; |9 s) \& ?
8.         } else {! S: R. s5 {' O' R. I
   
9.             temp[k++] = arr[j++];  t# _1 P. R9 k- J: J7 B
   
10.         }
    5 U, B, A9 t: d, ~: |! [* R
11.     }7 w- s  g& j# n- P- o
    
12. 
    ; w: O% Y$ B7 R, M# a
13.     while (i <= mid) {
    2 ]5 h: @, A  `4 E4 W
14.         temp[k++] = arr[i++];
    8 d% _4 d\" J% i
15.     }- S; v\" r4 J# d\" K0 B
    
16. 
    - F; ]1 M: w0 l6 ^+ W, P\" V
17.     while (j <= right) {/ [5 H5 ~% S& I- e
    
18.         temp[k++] = arr[j++];
    ; _% F( v\" S( j4 \  w( o0 [$ Z& K
19.     }
    $ |4 y3 }* h; Q6 r7 }\" P
20. 5 z; [  ?! y- R5 U% `4 H3 z  n
    
21.     for (int m = 0; m < temp.length; m++) {
    1 q/ t# i0 ?1 y5 r7 u1 q
22.         arr[left + m] = temp[m];
    8 @! \. r. M$ ^0 Z\" o
23.     }
    * B' w, Q# v- _& o
24. }
    ( m\" V+ K/ s\" [  S

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
; L( R2 C. {( _3 o  a
9 y9 P2 M2 ^: d6 U4 w' t3 M合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
: I' M! Q0 g- K" p1 S
! e$ @/ p6 ~: c* x需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
& p: ^9 S1 c  L
- s8 D5 f* y/ p1 B2 B这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
: V- I1 d% D, w$ @- n0 l
* T6 `! N+ z& ^7 m
+ h' \9 a1 A% ~: |- {7 I
. S" @# k9 h* j, S$ O9 W
2 b* S+ |) C# h/ W% V  m" r3 X. \3 J
# x/ B5 g$ u! @8 w% H5 O. z/ O: A( J% g' ^
3 H5 e8 l1 M% _' v
) p, k0 r9 s5 k8 n; W* o! {