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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
$ I7 ]+ S1 c% O+ {- \1 b) S
插入排序（Insertion Sort）
3 P0 o" e& |% `. @, L
5 V  e( b/ |% R/ N$ a% d选择排序（Selection Sort）

归并排序（Merge Sort）

) P; L+ V1 Q- r  ^0 L  J2 `  ]快速排序（Quick Sort）
: Z: P: T, Q7 ]( s2 ~$ l
堆排序（Heap Sort）
) A3 y/ Y- q" R4 e. U- l
) U0 {4 G5 c7 t1 B% D8 F一、基本介绍介绍
; ~6 N/ c+ k7 j( ^6 n. l0 R1.1 原理介绍
' [$ c  [2 E9 M! q' w9 l  T; w归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
8 o2 Y+ |$ p  a+ P# [2 ]5 N6 e
0 |7 @& v4 A7 j& H  @/ f归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

' t' F3 F' R8 }: \分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
0 S5 {' C- b/ L
& N5 R# G% d5 T7 y合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
1 _% q+ |$ B& l: H
! Z/ o- t7 H( ?5 p: e& K比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

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

( @( ]/ ]; ]1 v2 f将另一个数组中剩余的元素放入 C 中。

; B1 Y% O  f$ U: H! S6 w& k% L* O! Z归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
: {9 B, p5 C1 J, p3 h
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
/ [1 p1 t2 a& E$ U3 Q! M
4 ~& _) \* q* ]首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
' b% ~7 t- }4 v& I! V1 j, {! r
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
9 |, h2 `5 P. \: d' s
4 C. Y6 k7 m2 z" X对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
4 O- D1 ~- b, H: S2 o3 _" a, b3 n
6 v  Y- n2 d( r+ z! z: N6 K接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
" ?: w- V3 p" f* h
将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
% n/ @: q/ o; ?. K+ D0 M
& }9 x3 e7 p, L8 c4 A* _因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
! R$ `2 V: l! c3 J  p, Q) K, C# W% z归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

4 Q" i8 M0 }* e1 d这个复杂度可以通过分治的思想来解释。

6 B, y2 z# k5 @7 A, u0 _首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
, r: C6 b/ P  s5 b' Y2 V) O
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

. |' g' n" \$ ~: ~2 f+ y2 x这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

/ l5 \( k8 e. J1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
" b9 |# q' o+ e; p, G9 g
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
" q0 A+ x" v( e6 ?- N
( b7 a7 T2 s8 r' \$ ^对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
$ l; D6 _* X% F  b" j& s; f
1 |: k0 S; q- C总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
! [/ E2 g, u$ [" G2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):; d0 R$ f& W. A' R
   
2.     if len(arr) <= 1:
   / d2 |; Z8 M3 D3 u4 {' H  x
3.         return arr
   \" c  Q2 }, _/ K0 _+ p
4. 
     q6 T  b\" O/ m/ _& J& A
5.     # 将数组分成两个部分
   \" }& g3 j8 _% [7 p) [. ]( b0 ?% M2 H+ ?
6.     mid = len(arr) // 26 u, r/ b3 t0 n- Z. C% J# o! D3 S1 L
   
7.     left_half = arr[:mid]
   ! @# c8 O2 G1 }4 A% @
8.     right_half = arr[mid:]
   0 F4 g3 t9 p9 H2 X$ I
9. 
   ' p  X+ F. |$ D# z& E7 x' r# Y  s8 B
10.     # 对左右两部分分别递归调用归并排序
    % A\" t3 [9 Q! ?, U( \8 s( L# S
11.     left_half = merge_sort(left_half)* r0 \5 @$ E+ k) ~, L
    
12.     right_half = merge_sort(right_half)0 |$ \. {! r+ T: t, y8 C6 Y8 j
    
13. 
    9 J. v$ A\" N6 t3 X  [+ ]5 O
14.     # 合并左右两部分
    + |/ ?2 W# w4 q0 K+ Z/ ?) B* U* _
15.     return merge(left_half, right_half)
    * Q+ L: H) E* d1 X4 k  l
16. 
    ; w7 n- w3 Y5 C* F! K
17. def merge(left_half, right_half):6 _: u0 ^2 B8 q; l% E
    
18.     i = j = 0
      L9 R& z3 d$ Y\" H6 C% c& y1 `
19.     merged = []
    9 y* C: P0 C# E' Z/ l\" M+ k\" O
20. 
      v, Y' |3 V' f8 L) w
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中7 V( |+ u0 V: y! k& k\" V
    
22.     while i < len(left_half) and j < len(right_half):
    ! K/ q\" \3 D9 b  y3 g
23.         if left_half[i] < right_half[j]:' D\" A! i* o) t
    
24.             merged.append(left_half[i])4 u\" y* |8 M\" N* [! Y9 q
    
25.             i += 1
    / r2 @7 {3 J( f. J5 j' }\" G
26.         else:
    5 V# |8 Z$ m$ O0 D
27.             merged.append(right_half[j])
    . U8 {  q  }: C
28.             j += 1
    9 L6 `) f) }0 l. c* _$ p( ^0 I0 M
29. 4 `/ [/ Q0 \! l  b2 L( e
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    3 O6 f5 {, e) V0 t% X# t( \8 L9 c
31.     merged += left_half[i:]3 i8 V/ h  D- K3 o0 x. G4 j, U
    
32.     merged += right_half[j:]
    ; G  Q. I3 Y4 G) u, r* i
33. 
    / r$ u9 O7 N# j, @: U
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):7 C\" h- i0 S& z( g3 }& F5 ?8 |- M
   
2.     if len(arr) <= 1:7 w\" w5 s& N+ Y3 |& R+ b
   
3.         return arr\" J6 `6 B8 n$ @' r
   
4. / R$ i, w0 ~6 `6 B; c. Y
   
5.     # 将数组分成两个部分
   1 q8 {: L\" Y+ d; {\" n. i# L
6.     mid = len(arr) // 2
   . Z+ m3 Z1 O# z! S- y  M+ |$ l
7.     left_half = arr[:mid]! f6 N3 |$ b1 E/ b$ i1 N+ H3 Z
   
8.     right_half = arr[mid:]
   : C) v6 {, b+ R4 Z
9. 6 _: H! c% d8 G$ U. h
   
10.     # 对左右两部分分别递归调用归并排序
      M* L% [0 b( |- M# O% E& v) h
11.     left_half = merge_sort(left_half)
    # v1 b1 P8 V* Z9 f& i* z& [
12.     right_half = merge_sort(right_half)
    0 r! d9 n9 m3 T* t+ M! A; ?6 x
13. 
    ' [) o4 [) j8 x0 f6 N
14.     # 合并左右两部分
    $ E: @2 R, X, c1 l4 @! }9 {
15.     return merge(left_half, right_half)$ z9 z* y$ e9 E# @
    
16. ```
    2 n& F' _5 A8 S\" x% W# k% Z
17. % O( E; \0 l7 q: O\" j! D: y+ h. P5 Z
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。0 o) T- {: [+ J9 |0 ~; Z- O
    

复制代码

merge() 函数

1. def merge(left_half, right_half):1 _% ~) x; g+ F' _
   
2.     i = j = 0
   ! g4 g  X2 o& t( |8 E( [' O9 P
3.     merged = []
   8 }& C3 B; n( `3 u7 W
4. 
   2 \. j\" K9 |# D( ?2 a( @7 N( z
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   9 [% f! i' w; W
6.     while i < len(left_half) and j < len(right_half):
   / @# _3 m3 a; H7 `: ]\" A5 U% o; d% Q
7.         if left_half[i] < right_half[j]:! n: h( V7 b2 F( E, J# k  c; l
   
8.             merged.append(left_half[i])
   ( [' v$ D; v6 r; \- f; \9 d% o
9.             i += 11 d# q$ D5 S8 S( q& z6 w1 }7 k. g
   
10.         else:
      J+ y7 T7 r6 }! S, N! z. G. k# ?
11.             merged.append(right_half[j])
    2 q, T) V+ \; N5 u9 \. U
12.             j += 1\" x& b5 N! o& ]\" G' _: ?
    
13. : t% l/ p- C& e/ ]
    
14.     # 将左右两部分中剩余的元素添加到 merged 中' ]9 \; ?$ i9 Y
    
15.     merged += left_half[i:]
    ! o+ n; H# J3 W& Z7 o
16.     merged += right_half[j:]) q5 G/ V0 s/ b! ^8 ^8 L
    
17. & k3 [) g& S' H) H
    
18.     return merged
    5 q5 C1 m6 v. Y* ^
19. ```+ a! l0 m( q9 I  X
    
20. 
    + [, |% K5 O\" i/ B: g: Z  H
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

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

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

% R! @& `& T/ g" @对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
: e* P% m: L8 f1 C( u
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
7 d5 W6 B) P( P1 ]
1 p) d- n' c# b  t# p- T测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6], o+ \/ R3 b/ f9 ~# i: s9 a/ t
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
1 N0 w* a* z( ]& B2.2Java实现

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

1. public class MergeSort {: P0 o, P2 f! m
   
2.     public static void main(String[] args) {
   : H! D* V1 b5 P! Q\" B7 O0 F
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   # s( Z8 u: k1 }! Z/ |! r5 ?
4.         mergeSort(arr, 0, arr.length - 1);  v8 {' w' D2 q& U
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]2 P7 {' A* N$ D$ U
   
6.     }$ n' u! M# p, Y! z1 e! k
   
7. 
   3 U7 F0 o1 `) a' B, I1 N6 r$ V; Q
8.     public static void mergeSort(int[] arr, int left, int right) {3 O! z0 h' C$ l\" W% @: \% m( M# p' O' H
   
9.         if (left >= right) {1 I) c0 Q9 }3 O0 S! x5 y
   
10.             return;
    9 F! X: a( n9 g& n( ^
11.         }# V) Z. a, J) Q+ b( H  @9 v6 b
    
12. 
    2 u2 L) I5 q5 F* u. T
13.         int mid = (left + right) / 2;- F+ x6 L1 C& w' S8 {  u/ q3 Q$ n
    
14.         mergeSort(arr, left, mid);! s* i! D2 U0 @4 Z8 {
    
15.         mergeSort(arr, mid + 1, right);$ L. ~; h* i: }: c5 I- D5 D
    
16.         merge(arr, left, mid, right);# H, d: @0 `( E3 f4 Y9 a. y$ N
    
17.     }/ m  O; R/ d& V
    
18. 
      R0 o* Y2 o' _4 z- o
19.     public static void merge(int[] arr, int left, int mid, int right) {
    4 ^) n4 p9 e3 |: Y, t' U; p5 p
20.         int[] temp = new int[right - left + 1];
    : O; O& A' c7 C\" u& ^/ O+ y
21.         int i = left, j = mid + 1, k = 0;7 J* i* \1 y7 h# ?( C, J
    
22. 
    * ^5 k% {# B* G* c9 U) B& N1 y
23.         while (i <= mid && j <= right) {% r: D$ `0 R; @! R1 o' y4 T' C
    
24.             if (arr[i] < arr[j]) {
    7 _0 E8 ~6 @; H3 G
25.                 temp[k++] = arr[i++];# G\" D* W  J5 f- L9 R
    
26.             } else {! I6 _( i* u: `4 ]4 ?
    
27.                 temp[k++] = arr[j++];! X/ o8 G1 A. e. W% @$ N
    
28.             }
    $ t\" ]# Z+ T2 p$ h8 V# s) @
29.         }: f5 E% ?% W, D1 i, o7 D
    
30. 
      P' e3 H( R& t\" ~0 u- r
31.         while (i <= mid) {\" c- @! t1 P1 s$ Z9 V- Y) A
    
32.             temp[k++] = arr[i++];3 V, _0 j' B! ]) B& k2 y% S
    
33.         }( s# N9 [! I) s0 ?9 \
    
34. 
    6 u: |- ]8 {$ j, S, G9 @7 F0 A
35.         while (j <= right) {
    0 L$ @5 h, t+ Q. u' r
36.             temp[k++] = arr[j++];6 K- `1 M: W0 A$ K5 w7 C- B+ K
    
37.         }
    7 M8 K6 j8 X% Y4 q: h' E' m. b
38. 8 F+ B2 c; Y; X; o8 y# j. ~: f! w
    
39.         for (int m = 0; m < temp.length; m++) {
    & {1 n; X% f. q. P7 C6 r
40.             arr[left + m] = temp[m];
    . [; l# s) e. i- V: [. i& o
41.         }
      x4 X5 l& c' L8 U4 P5 B7 n: E
42.     }4 A: W) x; |- m
    
43. }

复制代码

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

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

3 J1 k; p( K# r8 f  y& RmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {  N& D8 r  L  w+ t# C
   
2.     if (left >= right) {) S5 N. ^9 r( w$ ~\" r4 J
   
3.         return;8 o& E% }# h6 ]+ w; e
   
4.     }' |# m7 z, h0 R/ q) v$ |
   
5. 
   8 ?' ~& S) y: a5 w# k# ^& G: Y
6.     int mid = (left + right) / 2;  `  M+ z+ h3 |4 ]1 h2 {
   
7.     mergeSort(arr, left, mid);9 N' M- C. d& |) B9 R7 X
   
8.     mergeSort(arr, mid + 1, right);  K; R+ p2 C) T2 \) m
   
9.     merge(arr, left, mid, right);: f. U\" g* X. \1 X9 u% \# u1 }7 [
   
10. }4 C' k* k. o/ M- q4 I7 w
    
11. 1 ]3 f6 I7 G0 W1 I, V
    

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
: L4 E( m2 Y# d
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {; e. M. b5 t: @, o1 z* g
   
2.     int[] temp = new int[right - left + 1];
   & N( R7 g$ B: g  s
3.     int i = left, j = mid + 1, k = 0;
   8 g/ I$ V1 f7 ~0 u! N& b/ k
4. ! m5 w\" _& \) _
   
5.     while (i <= mid && j <= right) {\" L8 M4 ?( T% A
   
6.         if (arr[i] < arr[j]) {
   * l7 R4 n9 U: J4 `4 G
7.             temp[k++] = arr[i++];
   ) f0 ?3 j\" w1 ^  I\" {3 p0 ]
8.         } else {
   ' z/ C) a3 c9 |
9.             temp[k++] = arr[j++];1 X1 c1 _8 ~  M- ]5 [1 b$ c) U
   
10.         }
    3 q( y\" K9 Q2 o+ [4 n
11.     }
    / Q7 W( X8 z- u, u
12. / `# ?0 a2 j. F+ Y/ u
    
13.     while (i <= mid) {
    ' ~- m) c! v- r% d8 L
14.         temp[k++] = arr[i++];
    : J( s# G/ x5 m8 [& K5 N+ r
15.     }* V5 I\" b% M  Q
    
16. 5 X7 ^6 _& G, f* S; E6 P7 D) s9 J
    
17.     while (j <= right) {
    8 R0 J2 r$ x6 e
18.         temp[k++] = arr[j++];/ N7 ^( q. ^, U4 L7 [
    
19.     }
    . f4 u7 Y9 T) j: P8 l8 z
20. 
    ( o3 V! M7 A' W' c2 \
21.     for (int m = 0; m < temp.length; m++) {
    7 G4 Y( P5 U5 P# Y9 j
22.         arr[left + m] = temp[m];( W) ~5 |# B\" N( a\" G/ K
    
23.     }% @/ S- q\" m. H0 P: o
    
24. }7 q, u* B) `2 a# }/ }
    

复制代码

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

. J& a1 P1 y8 [) B; r8 q, q% z" S: l合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
: a( ~8 {- |1 X7 y9 S! P2 R
* W1 a9 j' n/ F% S( M最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

" @; a6 @2 C5 t! ~3 V- h8 n* d' T' w需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
5 @" U, S0 R5 B! X* d) R
8 G/ N& p. @9 x1 J# k% V0 @/ K这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。


- O7 M& O, S9 K& {0 I$ ^- A


( `* ^  h' s( R& n4 L& `7 c' F0 Y# c

2 ?$ I+ `. z, `