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

2744557306

1 基础介绍
( h* Z" `8 n: p8 n$ V8 G3 o) n; O9 I, m排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
- S* i  d. J1 m# a; ~5 P: p
以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
  b6 O1 M) f" x" Q1 j2 v2 Z. ?% Q# o
插入排序（Insertion Sort）

选择排序（Selection Sort）

3 v+ k8 f- W) a3 _归并排序（Merge Sort）

: T! P/ r# H) g* j) J$ ]7 a' @$ t快速排序（Quick Sort）

堆排序（Heap Sort）

8 E4 m1 B9 ], d# s9 D% t一、基本介绍介绍
/ `6 V' e' c' X* C- T. q" j1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
( k; a+ T. @0 \! \- Y" F/ f
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

0 r3 |+ w6 u& K分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
" g6 }" W" O% \& ~5 |
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
* K% \$ y  }) R6 O
% r; {3 p7 ]3 D- q# |合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
# V0 d" n8 _7 d  |$ P8 f& S3 E* C
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

% a3 N1 _$ S8 Q# }6 |* G重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
/ f2 B# F1 B) n; X3 o
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
6 w. a; a- H5 b& D# ^7 J
8 ?$ E0 Z$ n% k% h1 V0 k# Q' X原理简单示例
7 H2 q( \" B; P8 J0 N以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
0 j8 E. p! ^( u1 N
$ z- ?% e8 R8 W6 Q- G  Z: Y' s假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
2 X5 j+ _& |, n2 ?
: Y5 |" p) p: K. x# [# X1 S首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
7 K" f1 ^! ~( v7 s1 y4 \5 c5 U6 Y/ C
  b6 O; C2 I" s: u8 v对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
* l$ H  g- w, C1 @, H5 E
+ q$ T" `5 G' i6 f对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
: }7 z( Y- H+ B4 F+ O% T) ~
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

1 j/ t3 w9 a7 x. w因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
- t: F9 C  R, t9 z
, o& P( g5 f( a4 F/ T* K1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
6 j/ B( Y) A4 z: t
这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
% w$ C; A3 l6 r! T, r7 F
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

. F, h- ?% g$ F* n& `# J8 A/ t归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

9 V- \5 T; w# ?这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

( \! u5 ?9 y: W/ Z: O" G8 D对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
, B" [4 b' v, E; p; v) {
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

; V$ I$ R; j+ \7 N. M2 j对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
8 h( A* Y7 i& p1 p
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
+ W* p8 d, r# g+ n
$ u4 c( ~* T# @* `* d对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
/ Q! v" ~8 O8 z* k
, O7 N6 P0 q* y( Z$ V总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

5 f/ Y0 _3 P5 Q# z7 v. c二、代码实现
: E) O- b1 _6 \8 s! ?5 H8 k2.1 Python 实现
% F/ ^/ q+ f2 [1 X$ T! K7 _以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):, u4 J2 ]. ^! B1 `
   
2.     if len(arr) <= 1:- M7 Z: [8 v' Y4 V. n
   
3.         return arr4 C8 n- I3 O& V7 I3 f
   
4. 
   2 R1 f' p\" a  ]( `
5.     # 将数组分成两个部分
   & G. Q; @$ E  j! c8 g+ |
6.     mid = len(arr) // 2
     i4 Q, R7 o3 H. z( Q* H8 T
7.     left_half = arr[:mid]& v3 B$ z' S\" ?8 m+ Z
   
8.     right_half = arr[mid:]# b! ?! k: X* e( R3 g8 g
   
9. 9 w* U' I8 F  R5 n\" p
   
10.     # 对左右两部分分别递归调用归并排序5 g# _4 u6 ^/ P+ P( {
    
11.     left_half = merge_sort(left_half)
    * _$ k3 V\" R7 W& Y: _( t( e! h1 H
12.     right_half = merge_sort(right_half)
    ' F# v+ I' ?! C& j0 @
13. : p. i4 ~, l/ s* i# ^: W) F( l
    
14.     # 合并左右两部分) o3 E2 w% p! q
    
15.     return merge(left_half, right_half). s- U1 ~! `- t# W1 w, e$ X5 f
    
16. , f9 h2 A! R5 a
    
17. def merge(left_half, right_half):
    , r6 ], l- D+ b1 {! A( {
18.     i = j = 0
    : n0 r' Q+ `% D; }$ x1 C
19.     merged = []4 i  i& g! J9 i1 h! e
    
20. 
    ' L, R( r3 M0 H
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中. l- G/ R  g& p% i5 P' K, `: W
    
22.     while i < len(left_half) and j < len(right_half):' K1 W) q4 q* k$ R\" l& Y
    
23.         if left_half[i] < right_half[j]:/ n  y) x5 o/ m5 e5 w+ o. C; G. w
    
24.             merged.append(left_half[i])
    \" N2 S9 L( U6 u) `2 }* b
25.             i += 1
    : A\" K2 g# q3 [/ i* [
26.         else:
    ; _( A- B2 J5 e& B\" X; C2 [
27.             merged.append(right_half[j])9 Q* D0 o. Q: ~( A1 k, F0 F
    
28.             j += 1
    1 x3 e* N% u7 o9 y7 ]; a) e* {# M
29. 
    ( u2 \( X% X\" n$ J% o, [2 m( ~
30.     # 将左右两部分中剩余的元素添加到 merged 中7 m; a0 C( t\" {9 J9 D+ ^; `
    
31.     merged += left_half[i:]
    0 ^# j7 U- h, E! o& x
32.     merged += right_half[j:]$ g5 Q% l0 \& A$ d! R# Q, _
    
33. 
    ! h0 x$ L. o2 t: F4 b- c
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   . y& {& U- Y5 E; T/ p, G
2.     if len(arr) <= 1:
   ( q3 G2 V\" K& U6 \4 J9 C5 I% r/ X
3.         return arr, s& N& ~\" F. h' G' Y
   
4. % S2 w9 @. D0 q
   
5.     # 将数组分成两个部分% o! b3 K, W# L\" l4 j' R' ~
   
6.     mid = len(arr) // 26 q1 Q4 `- e1 |5 r\" p
   
7.     left_half = arr[:mid]
   \" t7 _3 X0 U& l
8.     right_half = arr[mid:]\" i) S: ?, b7 S+ W
   
9. ( X' G' R\" l% P% v
   
10.     # 对左右两部分分别递归调用归并排序
    ' |' w3 ^4 Q/ z, a' A, ~0 t+ T
11.     left_half = merge_sort(left_half)3 s$ L& n* H* }
    
12.     right_half = merge_sort(right_half)6 V( @+ q& f: R. q
    
13. 
    - m/ _- ~' H8 S$ C
14.     # 合并左右两部分
    7 ~8 q) U+ w5 I9 d
15.     return merge(left_half, right_half). l; O8 o& }; j3 d2 f! X4 F7 g: [
    
16. ```$ J& D- g5 c+ i2 Z
    
17. 
    2 w% Z' z. [2 w5 [
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    & J; t: a. j' s2 Z\" U* n( l

复制代码

merge() 函数

1. def merge(left_half, right_half):3 k4 c; _/ B. `% t: p, P0 V! ^) w; p
   
2.     i = j = 08 P6 U* R2 }, Z7 }7 Q4 W
   
3.     merged = []/ E  U3 h1 K4 [: U, L
   
4. , s2 F- a: U2 |0 p& i
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中. u7 A; K* ?\" c; L
   
6.     while i < len(left_half) and j < len(right_half):: a/ w# Z0 a$ C; T6 T1 j& j4 T% q
   
7.         if left_half[i] < right_half[j]:+ |, L' r( s0 J2 E' K0 i
   
8.             merged.append(left_half[i])
   . s/ W$ E3 w1 }' ~
9.             i += 1, h6 l2 z7 ]- t5 ]
   
10.         else:; e! e& \7 T& K+ X( x5 K/ t
    
11.             merged.append(right_half[j])! L  Q; m+ [; q% N. W/ G0 Z
    
12.             j += 13 c3 m& T# y. I
    
13. \" q1 W8 L+ U& U# L5 p$ u) F) M
    
14.     # 将左右两部分中剩余的元素添加到 merged 中\" `. ]# o9 b, p+ ?
    
15.     merged += left_half[i:]7 J# S+ O3 d- m$ ^
    
16.     merged += right_half[j:]
    6 ?( z, U. l; \5 I0 h( G- O
17. 
    ' ^- D5 r# [* h! {5 T
18.     return merged3 O1 q! t; z% H. ^% Z7 A( L
    
19. ```- x' U; B0 r0 r9 B
    
20. # `, t& |& J$ |. F5 S% ]
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
) |/ [. w' X) m8 K
; ?8 j/ Y0 D: |3 ]1 ~判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

9 t8 ?9 \2 d1 }: l& K: X( \0 M将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
1 o. B9 ^* G7 d( Z% @
' A) U' ~5 C9 x: A' l  E. J6 y1 H. A对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

: T" ^' |& K9 j  f合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

; O9 w0 L5 c0 }) X* Q/ I% T7 e测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]% n1 F# I. j\" I9 i; o, y) G0 W3 s+ v
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {
   ( h7 |8 h0 J) A2 r% m  E1 K
2.     public static void main(String[] args) {( q; q8 l, P. e6 j* ~
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};- x! A3 a/ p6 w/ m& o6 H6 k/ k
   
4.         mergeSort(arr, 0, arr.length - 1);3 O; L# L* z; B8 ?0 u9 Q
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]* z; p2 w2 C0 {$ m5 v$ S: ?/ `8 \, w
   
6.     }$ }0 `: h0 z* O5 H# b
   
7. \" G. h, g) W5 Y0 v1 p2 v4 F
   
8.     public static void mergeSort(int[] arr, int left, int right) {1 d: e7 P- ^7 h& x, p) d0 z
   
9.         if (left >= right) {
   3 {$ u0 }7 S' x% g$ a. L\" P/ y
10.             return;
    4 i& t2 y8 f2 \8 V
11.         }
    3 W- y+ \% G0 n
12. 
    ) C* M. v6 X. n/ v; q% U
13.         int mid = (left + right) / 2;
    ' q, I* H6 N$ G  z
14.         mergeSort(arr, left, mid);  U2 c8 s  r1 I% N8 R- j  h$ N
    
15.         mergeSort(arr, mid + 1, right);$ _! d  j  d5 n8 i/ c! X( u5 k
    
16.         merge(arr, left, mid, right);
    ) V  s- c6 M6 N
17.     }1 [5 F9 }7 w9 N- a% V$ h$ u; O/ D9 e
    
18. 
    7 h$ I; U8 U\" ~  a+ x
19.     public static void merge(int[] arr, int left, int mid, int right) {
    ( _; m. ]# z) Q7 Y4 @
20.         int[] temp = new int[right - left + 1];\" ~\" b2 |. ?0 X4 a9 a
    
21.         int i = left, j = mid + 1, k = 0;) T1 Q( P2 s3 d# ^+ r' c& H
    
22. 
    ! v8 G2 A# E, ~4 Q5 T
23.         while (i <= mid && j <= right) {
    , j. y- A  X, b# Z8 s
24.             if (arr[i] < arr[j]) {/ ~# w' y9 t) m9 {5 Q, _
    
25.                 temp[k++] = arr[i++];) K; T. C' a% Q$ N* w
    
26.             } else {0 o7 J4 b0 r# U- M
    
27.                 temp[k++] = arr[j++];
    ! F; C9 L1 A8 a; K/ ~5 i, Z
28.             }
    5 Y1 ~& X- X6 c  \% b7 x
29.         }
    / [2 b3 t: d; V( }
30. 6 G/ V* `$ E$ K8 `: R
    
31.         while (i <= mid) {; w0 M3 R: d\" L& n
    
32.             temp[k++] = arr[i++];7 s/ i8 X& _1 z( @7 N4 \- ?3 I
    
33.         }
    $ {1 A: q$ n& ]' U
34. * ~! X; s8 u\" G7 K1 n
    
35.         while (j <= right) {
    6 r3 w: l/ m% z! M
36.             temp[k++] = arr[j++];
    ! a) Y1 K0 R3 g. G) |
37.         }) T3 ?1 ?: }. i# Q
    
38. ! J2 a1 \6 X* `6 K
    
39.         for (int m = 0; m < temp.length; m++) {
    * @6 `+ i9 {* D: c/ N
40.             arr[left + m] = temp[m];
    # J2 N/ q* \* b
41.         }
    # q  P\" Z! B7 t6 B/ g% C, |
42.     }) L- V  j* G  w# D
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   2 a! w\" r, ?; A6 K1 m( \* }
2.     if (left >= right) {
   1 U' @( \; F\" K! h5 F; ~
3.         return;# Z( N9 x: o% U: k$ Q
   
4.     }
   7 m: S+ H0 I\" N
5. 
   ! @0 t2 b' W- D  Z2 a
6.     int mid = (left + right) / 2;
   ' }, m4 v. e8 B& H$ I0 f
7.     mergeSort(arr, left, mid);
   ) A& s& }; J6 C& Y2 @
8.     mergeSort(arr, mid + 1, right);
   1 w* K6 T7 R- }  r# g- D8 E9 t
9.     merge(arr, left, mid, right);
   : @+ y- W$ l& z\" v
10. }
    2 E. m0 Q; w8 K4 r# ]( V, v; b
11. 
    2 m1 b7 j7 Y/ C) x; O

复制代码

这个函数使用递归的方式对数组进行排序。
1 v% v: }, N% b# [* B
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {
   + T0 H3 c\" l8 Y  V4 O' Q# Z
2.     int[] temp = new int[right - left + 1];/ U( q2 B+ l# ^% h& l. p3 K$ H
   
3.     int i = left, j = mid + 1, k = 0;) Y, R. H' _: l! T: T0 E
   
4. - @$ Y* [5 m6 b  Z4 B8 _) R* Z) ~/ F5 J
   
5.     while (i <= mid && j <= right) {
   ( }' J) {# s5 q\" s4 c$ \
6.         if (arr[i] < arr[j]) {
   3 o! l5 ]: n+ O3 U: A% s\" ^9 v) i
7.             temp[k++] = arr[i++];( \8 e1 o' w) D- N7 m8 A
   
8.         } else {
   ' D: y/ h: c# M8 |8 _1 n- }
9.             temp[k++] = arr[j++];) p6 i' V8 ~: g( m9 X; R
   
10.         }\" K0 H/ _4 y* s  p8 u9 m
    
11.     }1 ^9 E/ `. ]* R
    
12. 
    * @: i+ f1 Z2 O+ F( ]1 R
13.     while (i <= mid) {% s8 f! h1 g8 o+ z( H, `
    
14.         temp[k++] = arr[i++];0 o* c/ k: ~. T1 Y0 F+ j. r
    
15.     }
    . I5 y6 ]! [- u% ^3 H! O
16. ' U  E/ [/ u$ E2 Z+ b5 y: a& V
    
17.     while (j <= right) {' q\" S/ f* [9 q4 {9 \+ |
    
18.         temp[k++] = arr[j++];% u4 |5 x: \' t$ I2 X' q' a
    
19.     }  R0 m0 R7 S; A! o+ Z9 Q- D
    
20. 0 Y  Z# K6 S6 h( s7 K4 ]
    
21.     for (int m = 0; m < temp.length; m++) {
    4 U2 q% V  c; c/ Q7 R. I$ k
22.         arr[left + m] = temp[m];
    4 u* T9 t2 c) l. @6 X4 k
23.     }
      }& e4 p7 @  G: z
24. }, p2 t% Z9 s2 a% Y/ _! `
    

复制代码

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

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

( S0 N$ J& w8 l最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
) Y( b# G* u' Q) H
6 \+ l0 K) `# n4 l1 l2 o4 k需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
. `5 w& \+ S2 ]7 w6 b: z/ [
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。