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

2744557306

1 基础介绍
0 L+ e) B* w+ a: d排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
& p& h' ]! O! i, }5 ]1 J
以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
+ B8 S! I4 {* @
插入排序（Insertion Sort）
+ [) c" ]: i; b" h+ _5 s, [
选择排序（Selection Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

6 y8 M% g2 Z8 g/ R3 ~$ j% {堆排序（Heap Sort）

4 F! }) o% C6 Q% ~一、基本介绍介绍
- N* X9 a/ x+ p& B1 B. R1.1 原理介绍
( G3 _, w/ T, w/ z8 @7 A  m" d" `" ~$ [归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

4 m( A7 L: h1 R. f+ t% ]归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
, P2 {0 P' q7 R6 f9 B( G/ q
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

) f' m$ X5 ]' ?" P! Z合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
& z& y( c, c) j5 b- @
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

0 R9 C0 f* X8 Q! S+ Y定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

- i% H$ V) |' \% Y$ I- w- l比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
7 F: {3 q# l% h( q
) x% K" W: z  R) i& O! G  V% b重复步骤 2，直到其中一个数组的元素全部放入 C 中。

8 X$ {/ B( J2 e% g6 Z将另一个数组中剩余的元素放入 C 中。
8 g8 [. Z& e9 j' g
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

$ j* S  D$ {0 f% X, l' P2 ?原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
3 @& u( G& E0 h8 g" q5 t0 P, c
* e- y" d; w5 K$ f首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

! G3 I) d  x; ^对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
8 j9 I+ c6 V5 ]5 b3 ?2 \% O$ L
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

2 k% M1 y* H# Z6 l, s将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

. M: Y. m$ E; E4 }) w) l: z因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
) [' u) Q# z& W* c7 E5 j+ s
, R/ J# Y7 X- m  Z! P7 u1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
/ u) g. W4 ^7 z' H$ G
2 s% z# u! U2 K* y8 Y. {这个复杂度可以通过分治的思想来解释。
& m8 [- r, p* g! E2 @( I3 j
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
' ^. u, w$ B; o3 o- W: c3 x
0 }, E0 Q; Y" f  r# t( g/ w( h每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
* @; I& L/ R( s% k2 ^5 D5 s- L
) V8 o$ x- R3 E! z7 ?归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

( F' e2 f. p$ E, G  j) Y这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
' \4 u8 n( P3 H7 x% S
  r4 o& b  _' T1 I5 W1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

  I# R1 q4 o" l  p; L' b* B对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

6 M# J+ B! c4 w3 b9 v) D8 H对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
# q# @8 ^3 X1 m9 O5 u. G8 [
' l7 ~  N4 s' z, N+ ?$ q对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
* Y0 C7 ~: [1 i  H2 p) x
: a% ?* u) c4 U. w1 j( J+ h7 p对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
% W. t9 z' O; H( J
/ F  [3 C6 _- d' ]( c! }' ?总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
2 s5 Y5 b! a# n" d3 z, b
二、代码实现
. T% g# W9 a. @* m7 |2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   * c2 ]. J( ^- E0 y5 D9 C0 q/ X
2.     if len(arr) <= 1:9 H- j! w, N$ }2 f; b0 `3 `
   
3.         return arr
   # D  w1 a2 [  N: n/ M' _
4. 
   % i8 ~  {* u: r% H6 t2 S0 d+ u2 W# h
5.     # 将数组分成两个部分2 w3 P\" [( M) L/ v. r
   
6.     mid = len(arr) // 2
   7 `9 j4 i4 D8 b  g  e
7.     left_half = arr[:mid]
   4 ]* _6 K4 L  Z# R3 H
8.     right_half = arr[mid:]- p, t/ G( y1 D- X# W& F% e6 E/ H
   
9. , J- g6 B9 x6 ]) e
   
10.     # 对左右两部分分别递归调用归并排序$ I% f# |6 \  t+ O4 d5 J
    
11.     left_half = merge_sort(left_half)
    7 o& c/ V! Z) [
12.     right_half = merge_sort(right_half), J# @1 F4 h  C, G7 A+ \
    
13. 
    + c\" k  s5 [/ K- y% G+ e) G
14.     # 合并左右两部分
    ) u( }8 B6 I1 O
15.     return merge(left_half, right_half)\" X* s' O4 W. h% y  C
    
16. . O5 l* R% {! q\" x7 F9 D
    
17. def merge(left_half, right_half):0 F! Z9 a* r- ^$ a
    
18.     i = j = 06 }0 ?/ V\" N+ T1 T4 i\" m9 O0 n3 ]
    
19.     merged = []1 z( B3 L: V  r0 m* o
    
20. # y% M  I- P' [& W
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中$ e' O$ q\" O1 {8 n$ t\" E  t% Q/ {
    
22.     while i < len(left_half) and j < len(right_half):* c4 G4 k! |  f( t2 y3 K! h
    
23.         if left_half[i] < right_half[j]:# E. z/ Q+ c4 R% T4 N
    
24.             merged.append(left_half[i])1 [% U; x( Y- C, [
    
25.             i += 1
    1 a: Y/ m3 ]# H3 j
26.         else:0 B  n3 e. J: Q% q% Q- m
    
27.             merged.append(right_half[j])
    3 g' Q! A) e: h9 `$ H
28.             j += 1
    $ P0 _+ [! K' a: Q
29. # L6 b' ^) b' V+ N! {
    
30.     # 将左右两部分中剩余的元素添加到 merged 中4 {3 X. m9 @8 Y7 S) V8 P
    
31.     merged += left_half[i:]
    ; w$ g. G- H) a- u+ A; O( o
32.     merged += right_half[j:]9 h' G# W' x) _8 f# S2 S
    
33. 
    , S; v, Z, \1 o! N
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   ! @, K2 a5 k% z# Z& r6 G
2.     if len(arr) <= 1:) K1 F6 i) B) n\" x- p/ r
   
3.         return arr
   / i4 L* U' a7 M5 ?9 J; H! u3 h8 ]
4. ) c; L7 J$ y7 {0 O
   
5.     # 将数组分成两个部分& J+ y, ~) i! P! v- k: {4 ?
   
6.     mid = len(arr) // 2
   1 R( w+ V7 ]( h. l
7.     left_half = arr[:mid]# ^! z! B: @  E
   
8.     right_half = arr[mid:]- h$ v& Z. V; L& y% `6 q
   
9. 
   7 y  L+ e1 d) E+ J& v
10.     # 对左右两部分分别递归调用归并排序. n8 ?1 u8 C5 {! C5 w0 O
    
11.     left_half = merge_sort(left_half)
    . \0 _8 @3 k8 c& P
12.     right_half = merge_sort(right_half)' ~/ u1 r5 z2 U) Z( m9 `$ k
    
13. 
    ( m. v, c' Y1 o/ L$ J
14.     # 合并左右两部分  s; E1 Y6 A8 Z! L
    
15.     return merge(left_half, right_half)# U: x$ y5 ~7 v. ~! v( E+ G
    
16. ```6 c/ ]/ Q: }3 x' i* r
    
17. ; |# V  g7 k) b
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。  o, k& X+ K0 l) V' u( z\" M
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   % O  y2 }# d% U' V4 T3 y1 D* c& r; {
2.     i = j = 0( X$ \' x. E5 H5 `
   
3.     merged = []
   , f: K4 H) H& W* G
4. : P7 @6 I3 c6 C% g4 R
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中9 [3 n+ Y$ t4 u6 w4 o7 T4 i
   
6.     while i < len(left_half) and j < len(right_half):
   6 S* ]* b# p1 b# K: k
7.         if left_half[i] < right_half[j]:( @' s, }. V& o$ d5 Z9 z\" u' n
   
8.             merged.append(left_half[i])' ]3 ^  r  I, \3 j0 R- n
   
9.             i += 1
   0 G) x/ u/ O0 {! b8 r! ]* Z7 c2 ~
10.         else:
    ' }' u. \9 n3 w7 v: |5 e+ S, z\" }* M
11.             merged.append(right_half[j])
    4 g/ {( \. `6 _! {
12.             j += 19 t) M& o9 H+ L3 f. O: r9 _6 \; k
    
13. 0 r9 ^( f9 i7 Q  ~* n( j. X1 T
    
14.     # 将左右两部分中剩余的元素添加到 merged 中; k\" d  u+ J! e, x4 r9 Q7 @
    
15.     merged += left_half[i:]9 L% B: A7 ?6 m% J\" Y, s
    
16.     merged += right_half[j:]
    ) v0 P  r: S+ T4 O& c5 }4 a2 _
17. 
    \" l4 v3 F5 ~: ^
18.     return merged9 N$ f! N  @; y\" _8 a  e
    
19. ```
    7 g2 u\" N' Q! Y1 z
20. $ f0 L% e7 t- i  x
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
0 }  ?; C. C6 i5 W6 A+ C
* U. w! B' S$ K( H; ?$ i判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
5 A7 t! ]7 B1 q8 M$ X
- i9 h- c: h2 P9 [  S4 W/ y& W将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
8 Z6 v7 x/ U: k9 K
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
( q( @' G. ?3 ?# D& {+ E
5 L* j! a1 r  ~. v. Y测试
+ V3 d9 b% ^( H0 U! G$ u在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]# P' [+ X. j! ~\" \( d
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   5 Q: W; D- j% S4 S2 E6 _7 w( @
2.     public static void main(String[] args) {
   4 d+ U4 Q% S% D% C; h
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   5 K$ z; l7 V\" Q+ G; ]
4.         mergeSort(arr, 0, arr.length - 1);
   ) O0 c3 t* {6 ~/ ^9 q) z
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   * v5 s3 i: X1 X9 c
6.     }
   ; X$ |  Z* j6 \9 @4 m
7. 
   8 A( r. X' h: H- C; x\" {
8.     public static void mergeSort(int[] arr, int left, int right) {% x6 i' f3 C# N5 Y' m3 S
   
9.         if (left >= right) {
   / I6 N5 P8 V! V4 A( P
10.             return;
    ) S9 P! U+ o7 W  m
11.         }
    : n; a! y- q, X+ G6 X/ I
12. 2 f1 n. b. ], Z3 l) {9 h+ n/ o3 G
    
13.         int mid = (left + right) / 2;8 m6 Z. u& a9 J! ~
    
14.         mergeSort(arr, left, mid);
    ' A% I4 D4 S, q6 a
15.         mergeSort(arr, mid + 1, right);
    4 x7 V9 x5 H\" f: G1 g
16.         merge(arr, left, mid, right);
    1 d& v4 B! p' Q9 |. w
17.     }
      y- B5 |2 @3 p
18. 
    1 U4 q3 e- o) p/ I0 {( }  v
19.     public static void merge(int[] arr, int left, int mid, int right) {
    , H( L1 j0 J* x3 s  H+ p# a8 V2 M
20.         int[] temp = new int[right - left + 1];
    $ L8 \$ P& r! T+ y/ H1 e3 J
21.         int i = left, j = mid + 1, k = 0;) @* u4 k- R+ ?8 n8 i: s5 n) H4 A
    
22. 
      p\" ?* e: W1 m; {; {) T
23.         while (i <= mid && j <= right) {8 Q. \8 u7 b5 t
    
24.             if (arr[i] < arr[j]) {
    7 Z- i  r% m) O& \
25.                 temp[k++] = arr[i++];- }# x: J' o3 x  g- u
    
26.             } else {9 Y6 k: a+ |( D
    
27.                 temp[k++] = arr[j++];
    / z/ t$ {, m7 y- P7 r4 g$ j
28.             }
    7 T) ^4 w7 ^. J/ u/ Q
29.         }0 V; ^  g& ?5 }1 H\" r0 `
    
30. & ^+ F% T2 `0 T2 j6 C
    
31.         while (i <= mid) {
    - C2 n3 u- x$ l5 F- @. w
32.             temp[k++] = arr[i++];& `' r! t' z5 O3 P  v
    
33.         }. G  @9 R8 f; K) i+ T6 [- n
    
34. 
    3 b) b2 Y, a# n  V1 n. V
35.         while (j <= right) {
    8 I5 |! D0 l4 F: a
36.             temp[k++] = arr[j++];' `\" s( |3 \2 B& J$ F& K
    
37.         }
    $ E: z9 Q( B+ l2 s3 N
38. 
    2 g% F1 @6 O7 U; ~7 P2 _
39.         for (int m = 0; m < temp.length; m++) {2 v9 V# v' P4 c+ u8 Q& R. J
    
40.             arr[left + m] = temp[m];
    . X& D+ ]. d. k5 d- n; q
41.         }
    \" \$ Q& |1 d* C
42.     }. @! C- d( u4 g# h- t
    
43. }

复制代码

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

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

7 Q- v# G! \- c* R9 q: lmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {- e3 F8 a; v8 j9 Q8 q$ T8 z
   
2.     if (left >= right) {\" D0 U5 O* E6 r! r5 Z# }  j  e
   
3.         return;. Q1 Q\" ~- c\" O1 V
   
4.     }
   * ^; W# ?, j3 o8 [8 a; ^% p
5. 
   2 b$ n3 K6 ^4 B) t) }; }1 r, s
6.     int mid = (left + right) / 2;; K0 L( Q  ]0 |) l
   
7.     mergeSort(arr, left, mid);' }0 a1 \( R' g  T2 v- s0 F
   
8.     mergeSort(arr, mid + 1, right);
   / o' W) e- \8 _
9.     merge(arr, left, mid, right);
   ! b\" u, w7 I7 M: B\" p  w
10. }
    % _- K$ x0 e6 X
11. % i9 E+ l2 A8 }9 a\" M0 E, R
    

复制代码

这个函数使用递归的方式对数组进行排序。
/ w& {. p4 L* ?8 V' Z& f) Q/ p
5 w3 |6 `4 A. G  [$ t" U- c对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
2 {. }* y5 o/ ]/ I# p( G% H) E
. \1 \' q$ a9 F8 Q" `  s3 k! A最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   % e8 M* J/ n4 a/ F, H4 {9 i9 n\" w. g
2.     int[] temp = new int[right - left + 1];+ h8 K1 b4 O\" c, ^- i; W
   
3.     int i = left, j = mid + 1, k = 0;
   7 P$ K: R3 H& r1 \$ G0 B* n
4. 4 N: p& s+ J7 l! b
   
5.     while (i <= mid && j <= right) {
   1 T* H\" m9 X, l
6.         if (arr[i] < arr[j]) {
   9 v* ~& j+ h! F' A
7.             temp[k++] = arr[i++];
   * t/ v1 \% k- X; u
8.         } else {: e  N: G3 f9 [6 Y1 h
   
9.             temp[k++] = arr[j++];
   & M+ J/ P! K, y* \# h
10.         }# b6 h/ b  l, g4 h8 q
    
11.     }* V) p* x/ C9 ~& W* K& e: J\" Z
    
12. 
    2 V& \3 q6 V7 M  O+ B, f
13.     while (i <= mid) {% K3 Y9 {3 z& S) g
    
14.         temp[k++] = arr[i++];4 W7 M4 X2 d# \\" E; N2 D
    
15.     }
    # t% l, x$ t, K# h; B
16. 
    % D$ ]3 k3 [4 [1 C
17.     while (j <= right) {
    . S4 r. j- [2 c* {
18.         temp[k++] = arr[j++];
    \" a3 P0 }  t% f8 ^8 x/ X
19.     }
    - H  A2 N# E3 g' _\" e0 z
20. 
    5 ]; F$ I% P* N) P4 n) v
21.     for (int m = 0; m < temp.length; m++) {5 U$ p% Q+ \2 B& E2 E% `\" b
    
22.         arr[left + m] = temp[m];0 l& Z4 H/ ^' l( S
    
23.     }) ]& Q* {1 Y% V+ {$ }  C
    
24. }
    + d) f+ s. P$ |9 E: Y2 q, r6 {1 |

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
4 g% N' l- N6 @
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

( a& j9 _$ _# W- j最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

% z! V5 h- L7 }7 f1 g: K9 s需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
: }$ K% b  {+ K1 I9 W5 \* |
6 _$ u; O3 v. X" Z




0 ]- z9 ~. k5 h/ Y( _