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

2744557306

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

- h4 W/ v( l8 o3 [; m以下是一些常见的排序算法：
' q; t0 U1 ?! Y! b
冒泡排序（Bubble Sort）
3 F+ `, f- k( E. l
插入排序（Insertion Sort）

( A& ]" ]: G0 Q* Q2 X: Y  ^9 D( @6 o选择排序（Selection Sort）
6 K/ g) E1 V8 e. [" K- N
归并排序（Merge Sort）

快速排序（Quick Sort）
4 ]- d+ l8 p9 N4 x1 I
堆排序（Heap Sort）

+ l9 n9 u8 X- L# u, E9 s  O7 U一、基本介绍介绍
1.1 原理介绍
2 p" j0 f; C+ E归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
  u* ?! W5 v& Y2 S& i" `# s
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

" R4 ^, D( |; C& ]  i+ [+ V( [合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

, t: K; M: ~- y3 m$ a比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

3 T9 m- k8 ?: e  I* w重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
: \6 d1 h/ ~( u% o1 M
2 q' a* k6 A# D' r2 G4 l归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
" F: j: o, `9 o2 N$ g# t4 [
# l  e8 ?& F; g8 q9 m! ~5 y% G假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
2 Y, W# ~# q( R) X$ g, u) p
' E$ A  t5 z2 p8 Z# n: {2 g$ A首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
1 T' B$ L+ ^4 @5 t5 Q6 I
' p, s/ X, _; p, s# c对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
; v- e" r3 r' ]0 H1 }# c* P, |
0 H; O. f" l1 U7 t3 W" q对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

  E- Z9 g* M/ {( b' T接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
7 M" {4 B% U0 x8 s3 |# o; V  W% i
将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

% u; Y  ?% B- A5 q. S" s因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

5 U9 C; b$ ~' M1 |7 H$ I每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

( F% o  P; Q2 A+ P* R! u归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

7 g6 Y4 Z' ?; S+ y, K2 @这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
6 \# ]: I2 ]% s' f7 c" A7 J
2 S9 T2 K& w" `" z0 R1.3使用场景
5 J5 U+ U8 i4 Z  [+ w归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
, [% {" Z  y$ U0 L2 s3 Y  D
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
# X& D* n6 c6 v% s- n' d: ?
# K! _3 b) ]; B0 f& `4 |对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
% M3 A  F" g" s! P- `
! V! B3 p% ]& Q0 S( F6 R对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
/ k# M6 Z0 t7 N; \# L
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
: ]4 o7 L2 I- f: \* j# R
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

! m2 P% W9 |" C3 e6 \( q二、代码实现
2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):- p+ K3 T! m- A7 E
   
2.     if len(arr) <= 1:5 z2 j3 U$ X. x$ @% G$ ]/ w+ X
   
3.         return arr
   # Q/ x. l: y8 C( S1 K0 y
4. 8 E, A) ^$ @( q: K1 T1 g3 f8 K- l
   
5.     # 将数组分成两个部分8 W, ?. @\" d4 b' q
   
6.     mid = len(arr) // 2% l0 r* j0 V3 Y3 G# o% i
   
7.     left_half = arr[:mid]
   ( y\" U* x. K, E$ s8 t
8.     right_half = arr[mid:]
   3 ~/ _2 b% _) ]
9. 
   2 c3 l% f$ a9 a$ L
10.     # 对左右两部分分别递归调用归并排序
      S. {0 H+ r\" \! b7 x7 y\" Q3 w
11.     left_half = merge_sort(left_half)
    : E$ `  v* L: S- Q
12.     right_half = merge_sort(right_half)( x! U% @+ n* v+ M
    
13. 3 p: V: L& m6 T  l7 X
    
14.     # 合并左右两部分# M2 d1 f+ T9 z3 W) L
    
15.     return merge(left_half, right_half)
    5 f$ V, K  P+ @! Z: m- o: Z
16. 
    9 e5 z! W7 W0 H5 Z: b. q2 R
17. def merge(left_half, right_half):# v+ D/ M! i) P4 |8 w2 A# [
    
18.     i = j = 0
    ' i5 o; P' L2 q
19.     merged = []
    8 V6 Y* t2 ~% f5 v
20. / O6 t! i7 Y% c/ f\" D1 Y
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中% v0 ~0 N+ \8 I0 S: f$ W( ]* n
    
22.     while i < len(left_half) and j < len(right_half):+ I7 Z\" o3 h0 C( }7 `5 I
    
23.         if left_half[i] < right_half[j]:6 Y, e* u' E% ~9 x. o- B3 e, I
    
24.             merged.append(left_half[i])7 Q6 r  `/ r% D, j
    
25.             i += 16 ?2 J2 P  g' w( Z  W7 S' q
    
26.         else:2 w9 v\" ^. `4 ^0 d& w  k( Q
    
27.             merged.append(right_half[j])+ u* b7 T4 l; A0 Y  R, G% B
    
28.             j += 16 m) `, [6 Q2 s: w\" N, {: l$ S
    
29. - v  w2 q( c\" o\" W' ]% P1 S* L9 B
    
30.     # 将左右两部分中剩余的元素添加到 merged 中\" O& Y9 Z3 X' O+ i4 H
    
31.     merged += left_half[i:]
    6 a6 v; K; O4 b. H
32.     merged += right_half[j:]
    7 E, B* e! k2 `\" D1 h7 k% B6 i! {
33. 5 }# U4 d\" Y1 W1 Y8 P+ T
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):% |$ Y) m9 j+ c9 Z
   
2.     if len(arr) <= 1:
   \" i  r4 l! C: i- N
3.         return arr
   2 y2 Q0 @% W- f7 Q2 ^  v
4. 
   3 Q- _. @' ^! F0 [- E+ n( U
5.     # 将数组分成两个部分0 N- M. J3 n9 D. I/ c
   
6.     mid = len(arr) // 2
   ; i2 B3 E/ z& W\" R( Q9 P' O
7.     left_half = arr[:mid]# [1 `* b1 ]7 W7 J( N
   
8.     right_half = arr[mid:]
   ) r8 M5 @& _6 Z! r
9. 
   7 |, `& z\" m; P2 X- \# P! r
10.     # 对左右两部分分别递归调用归并排序
    . X5 m2 ^# J; p' C# O2 R. |
11.     left_half = merge_sort(left_half)
    \" v7 o\" ?\" ~9 g9 {$ h) l% O
12.     right_half = merge_sort(right_half)
    7 O2 ~+ u% m! F' v( Q
13. 
    4 y* r1 R( {/ w
14.     # 合并左右两部分; C+ I1 y/ z* L( ?
    
15.     return merge(left_half, right_half)
    $ }2 Y$ \, G8 I5 M
16. ```
    ; S( {- _  B9 N1 z. O$ L
17. 
    ( P) d; W- b5 i6 t1 N: O
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    # Y* P  K; n4 g. A; v/ r+ D. \! G

复制代码

merge() 函数

1. def merge(left_half, right_half):1 S6 r  Y& D7 c% _; R, I
   
2.     i = j = 0; y  F7 G: _) \
   
3.     merged = []7 o. S8 i: H4 q0 B! k
   
4. ) E0 `3 r8 L& R) {9 C3 r6 s
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中  k) ?  T/ b7 B/ L  N7 D
   
6.     while i < len(left_half) and j < len(right_half):
   3 k+ |7 p/ e\" T8 H5 W
7.         if left_half[i] < right_half[j]:& Z, v/ G$ X. \3 i7 L6 l
   
8.             merged.append(left_half[i])
   ; i# W3 t6 T9 U  Y7 T8 v6 t! V
9.             i += 1
   % l) v\" {6 j' b( R6 o, g$ C  w
10.         else:
      t- \# ~+ p% X+ o) X+ U6 l/ s
11.             merged.append(right_half[j])- c3 F& O& y& X' ^* x
    
12.             j += 1
    8 u* s3 J, `- G; j4 @/ N
13. 
    1 t\" J) }' ]  [% F+ c. ^4 ?' c- v
14.     # 将左右两部分中剩余的元素添加到 merged 中8 J# e$ g  k/ F* e& n7 c$ r4 O  [
    
15.     merged += left_half[i:]
    1 Y8 I5 j3 s3 r
16.     merged += right_half[j:]( n. c% v2 i8 j
    
17. ' Y5 \( l& ~1 `9 f+ r# m
    
18.     return merged
    2 [: Q2 h1 E\" N& p' u
19. ```
    / J0 Q0 w; q0 k9 U# l
20. 
    & K& Q! ^3 c6 W( U6 @
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
  T* k' i: Z- O7 a5 g
7 l* V( {+ G4 {0 n. h# y) [  H判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

+ ^( T. n1 p, T8 ~' Z+ R$ v将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
  n+ ?4 I# e1 E+ n* I
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

, u) J" D+ \/ }" C' g: a* m测试
2 {7 `9 q( a0 ^' O7 j/ o- g在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]4 k- Z6 H; r0 B. h. }0 Y
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {
   5 n% }9 H; i1 d: R; i* |0 s
2.     public static void main(String[] args) {
   ( x* q9 S# t; W1 P\" `4 Y$ j, j- \
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
     S* N( w+ [: w* l) r/ K) \
4.         mergeSort(arr, 0, arr.length - 1);
   / K\" o1 _! ~( K
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   # }: R  v9 y0 ]+ j4 p' v
6.     }+ y0 c1 t3 I; K1 L
   
7. 
   & X: E9 G1 x* N( X, ?
8.     public static void mergeSort(int[] arr, int left, int right) {
   3 Z6 _1 s. M; Y3 M9 n* k
9.         if (left >= right) {* f( ^% U1 C7 ^0 ]
   
10.             return;
    - f4 K8 A* V# v# v: R
11.         }6 n9 J3 o# y1 K6 \$ u9 U* L
    
12. 8 u: L& L- ?. @, l0 f
    
13.         int mid = (left + right) / 2;
    ' d8 m/ E3 }# r6 r: U
14.         mergeSort(arr, left, mid);4 |4 T9 b2 m% \1 V
    
15.         mergeSort(arr, mid + 1, right);
    $ k  h; w* q, Q' n) u! ?\" g0 P, a1 l
16.         merge(arr, left, mid, right);, U4 d& a& P8 Z9 @5 Y
    
17.     }
    0 x$ j' \1 G' }7 i) r& `  ^
18. 
    ) K- I! T& b2 J; X3 e: f4 z: ]2 z
19.     public static void merge(int[] arr, int left, int mid, int right) {
    : X  X6 Q  ~4 F7 M+ R( g6 H
20.         int[] temp = new int[right - left + 1];3 }/ Y3 ~( a\" A0 }& Y
    
21.         int i = left, j = mid + 1, k = 0;
    5 Y0 h# N) m. \\" t' L; S' g8 w; ?
22. 7 t1 @* d1 k( N
    
23.         while (i <= mid && j <= right) {
    2 o5 w% y' b6 ^1 B  w1 l\" w, h
24.             if (arr[i] < arr[j]) {$ Q: {% Q8 K+ t# Y\" P9 }/ `
    
25.                 temp[k++] = arr[i++];2 N) E\" H\" ?6 G6 c. n7 z/ j& {
    
26.             } else {4 `& S- v, A% @: j; K\" D& T
    
27.                 temp[k++] = arr[j++];
    $ ^2 l& _8 Z- n1 X
28.             }
    7 G  U, a* ?9 c: v
29.         }5 Z( ~& W  w/ C2 V; E3 V2 p. i
    
30.   L) O\" x3 a: e! |: Y- `6 q+ q
    
31.         while (i <= mid) {. }3 l0 x& E7 o
    
32.             temp[k++] = arr[i++];
    0 B& F, M! P( }9 g6 L8 J
33.         }
    * ]) ]( {% u( ~6 @+ D
34. 9 L' b$ @3 W2 G) V
    
35.         while (j <= right) {
    / `- S0 l- L; {. s6 q: w: O( t
36.             temp[k++] = arr[j++];
    / f# |& T5 W( I
37.         }
    / y6 D7 L0 Y1 A: p1 w) h, }3 r4 J9 j
38. + e  z( G& }- ~- ^4 \0 }: m+ V  _
    
39.         for (int m = 0; m < temp.length; m++) {; j! p, `: }5 w. H
    
40.             arr[left + m] = temp[m];1 \' V) t/ S& T8 ^, P% Z( b$ ]
    
41.         }2 o( t) d8 k- D6 _6 Z
    
42.     }
    ' [4 K' I& g! v( S: d: z3 f
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   9 K5 Q4 q0 x9 {# l
2.     if (left >= right) {
   . b' d0 M5 A\" V# }# Q' v
3.         return;0 c1 c  D: M( C\" Q0 g; o6 b9 G! C
   
4.     }
   9 R$ }: f( ]- t5 t$ B
5. 
   9 o+ P7 \\" O$ X) ]
6.     int mid = (left + right) / 2;
   ! B+ F: j% a; y
7.     mergeSort(arr, left, mid);\" U: |  w0 a9 T9 Z9 x- N* w2 V
   
8.     mergeSort(arr, mid + 1, right);
   ! x! `1 j2 `3 y) u1 T\" u/ Q
9.     merge(arr, left, mid, right);
   , m: G; c8 P7 k5 s' j
10. }1 C8 g; V9 j# l) R, [% B- U
    
11. ) ^& {: B\" o3 a9 G: V, C\" a: m1 E
    

复制代码

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

: ^1 \8 n. p9 s* j+ c: l对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

( G) g0 h  H6 J: ?8 R最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
: U0 v* W. L- c/ g  ?, p) Emerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   . M: U* ^% P9 Z, s/ r
2.     int[] temp = new int[right - left + 1];
   8 i' W\" Q9 i8 U; u1 q& U3 v7 M* v
3.     int i = left, j = mid + 1, k = 0;# l\" o* y4 y  M6 d7 t4 e
   
4. 
   1 G. h! s6 o% o1 ]  o. l0 D2 ^! Y; ^
5.     while (i <= mid && j <= right) {1 q) h; j$ t+ `- R
   
6.         if (arr[i] < arr[j]) {; f6 D0 ~. l: \
   
7.             temp[k++] = arr[i++];: k4 y! P* a- J6 @& m
   
8.         } else {2 F, [% s! a\" C: T5 |$ x4 a
   
9.             temp[k++] = arr[j++];
   ( G( B7 a: y& i/ n& g/ a
10.         }
    \" i\" b& S% S. N$ m  ^8 ?+ F. f  O7 X- P
11.     }! H. e- G( s; Y8 Q; O; Q
    
12. 
    , |* @( g3 |5 t$ p
13.     while (i <= mid) {- D# p/ R( q% S9 l8 Y2 z
    
14.         temp[k++] = arr[i++];
    ; i) ^4 N) e8 i' z& V  z' i
15.     }
    ) }% w! m; x0 \. Q1 T. T, y
16. 
    ( L' U! B, L  b9 t0 L
17.     while (j <= right) {
    % f3 w# b' E- [, |8 s- s
18.         temp[k++] = arr[j++];! j6 X) J; _\" C& l# j. ^
    
19.     }
    # C2 R$ r5 W& m
20. # ^$ \! j, S' d8 q+ K
    
21.     for (int m = 0; m < temp.length; m++) {  ]) F$ e% e' A! j; B. T) P
    
22.         arr[left + m] = temp[m];
    % P* {' M/ c0 a- O\" J5 C( L6 x
23.     }
    7 X; h$ ~4 w\" e- V$ e5 p1 i
24. }1 q5 q; C: N: Z\" X+ p* \
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
8 K7 X( S' z* ]6 D1 O6 r
3 O- K7 h# g7 u5 S3 l2 n, z* u合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
9 h/ c/ e; M1 b$ D  d( F+ [1 \4 M' L
5 [& z, K& V; \# ?最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
  L+ `6 h) j$ A; z* a& I" X& a
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

  J: |0 @: F- O( x2 ]

: M/ E$ d+ {" z" l

! O0 u' ^# {: N2 l

) x& e% K+ C0 L