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

2744557306

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

2 _3 d# v! A5 J9 `( T+ {以下是一些常见的排序算法：
) o4 Y2 D4 q5 a. R/ Y; @! Y
冒泡排序（Bubble Sort）
/ s4 e$ Z4 |0 P& U4 V! a
插入排序（Insertion Sort）

选择排序（Selection Sort）
6 F& \3 P: ]* H: M5 i7 Q! ~
1 K2 ^% x3 |3 X3 P9 `6 V) J; a归并排序（Merge Sort）
0 [* \7 l3 ^- k+ i# q& k
快速排序（Quick Sort）
: d3 I) Q. U2 x# D. Y
堆排序（Heap Sort）

) T& H, X1 i+ ]3 c9 |  a% O7 d一、基本介绍介绍
' V8 _& V' I; }# D1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

& a* a# F- g0 K* X/ Y归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
5 O0 ?, i) Q0 e3 Z
* t6 ?% l$ c1 ~3 }8 j/ j8 y分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

8 ]* W" V+ r; b: \) N, Q合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
. q8 c' U+ T, h1 Z% d
1 ~) n9 {% _" j6 r定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
6 q3 R& N  w- q2 P7 `
- u( ]2 T9 P* b比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
5 ]: |4 B% @) `. T& K9 V
/ j7 \: \4 J1 x/ I重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。

$ `2 j4 J' L* U归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
' ?& X3 G9 N" B- d0 F
5 x, d6 l7 k! D6 K原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
7 u/ H) u* `. u( ?! K7 W, w4 e
* d6 W) i7 H* U+ h# k; {! E8 ~假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
7 k' y2 h& o  Y+ W+ L8 J. J2 v1 y
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
: A0 g  O% N, p0 `/ ~: l
4 [6 x1 T9 a0 K% }接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
. h% d7 M: {) Y8 O3 H# x- T& m
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
, V# G; F5 x' {- f
/ L4 ^) }9 b( r$ [5 p& K4 ~4 a1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
/ u9 t! D- `6 O  R$ g3 v
这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
: q7 M8 y" d( Z% M: c, j" \' U* f
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

0 `% I& x/ n& [! D9 ?9 J% b) {+ ~7 x这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
/ Z. G& t0 l4 q' [) Z
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
7 A7 a; O8 w4 R* t# Y
1 }9 d+ v4 f6 |+ x( d: v7 y; O对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
# R! j8 _! }; Y, ^7 X9 u! N
. I. G4 ?. u  Y- h. P" M对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

- f% K; A& v! z" `! O3 L对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
9 b/ d$ ^* [3 q8 y9 ~
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
0 h  M" b5 Z' |% U9 I3 n$ K
1 G" O0 v& q0 ]7 S$ B对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
0 I" W0 A2 v: y9 }7 |; o* O+ V
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
! p$ V5 E: E7 B6 R& I. X
2 T  N6 w6 o0 m- z) b: ~二、代码实现
3 s. y: t, r2 c, Z2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):% G& }- n# a, A( X$ P- \4 r
   
2.     if len(arr) <= 1:
   4 S) F1 i7 B5 z1 W
3.         return arr
   & Z. E$ q\" u! ?: l: o
4. 
   % t8 K! t1 ^: a8 c: e/ Y
5.     # 将数组分成两个部分; m9 H9 v# l  G- f
   
6.     mid = len(arr) // 2
   & C* [. d( H! c3 }3 y$ D4 a
7.     left_half = arr[:mid]
   ; U2 N+ W# R; M; N1 M\" Y
8.     right_half = arr[mid:]/ S4 K$ B) `. \& Q- M. C: s
   
9. 4 G) _2 B( F; N' O
   
10.     # 对左右两部分分别递归调用归并排序4 ]. m. }& k( g6 N3 R9 ~' C! s
    
11.     left_half = merge_sort(left_half)
    + d% D% w6 W3 h6 y, n9 H
12.     right_half = merge_sort(right_half)
    ! e& e' R% D2 N9 \7 n0 R
13. 
    % _9 L! [1 ]. Q' z9 D. |5 [
14.     # 合并左右两部分+ m4 u# n6 A& F: {) n7 @
    
15.     return merge(left_half, right_half)# Z. C8 m* Z8 E& q# O# N
    
16. 
    $ z; s  Q( U9 Q, c/ a
17. def merge(left_half, right_half):5 m+ d, E' x- P, M: Z2 c
    
18.     i = j = 07 L+ `8 f/ J7 u3 H( b0 w$ ]
    
19.     merged = []& k( \( D# s, X2 Z
    
20. 6 R$ P3 R; [9 t4 L. }
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    $ j$ o5 ]4 t$ [! j1 p% O
22.     while i < len(left_half) and j < len(right_half):
    * O% C* T8 H8 e9 ]\" v
23.         if left_half[i] < right_half[j]:
    ( t, l! ]7 N- Q6 ?. r/ y
24.             merged.append(left_half[i])
    ( }, C, L3 y* a& d& \( g
25.             i += 19 ^( l9 N; Y6 m) f1 q
    
26.         else:
    0 _4 Z9 z- T2 W. D3 `
27.             merged.append(right_half[j])
    1 w% T5 [, c) e7 g& R
28.             j += 15 \% n0 v0 x# o1 K* N\" q% [9 g
    
29. 2 [8 ?4 A3 Q2 d) B' D
    
30.     # 将左右两部分中剩余的元素添加到 merged 中9 m) a% V; v  ~, q* L& r; f
    
31.     merged += left_half[i:]
    7 O; \8 @. b, A$ s
32.     merged += right_half[j:]
    & K/ f2 ~7 ]6 \# Z; c$ j: u
33. % b8 F& k+ Y% b# B4 b% |: i; L
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):- n/ Z) ~% {; R) j4 A$ h% m
   
2.     if len(arr) <= 1:& S8 C1 f\" L' }- s3 U: _
   
3.         return arr; N5 m9 D' {& a3 s( N; [5 d) U& V6 d! H
   
4. 2 W# m* y; l5 T' w! B) V* e4 N1 A
   
5.     # 将数组分成两个部分\" d* t$ H. C# z
   
6.     mid = len(arr) // 2# ?; y\" C: t# p8 ?2 D/ W
   
7.     left_half = arr[:mid]6 F& U9 b4 S\" `$ u% u: j4 b- @
   
8.     right_half = arr[mid:]
   ) d8 b4 ~0 u9 b% W
9. \" i# ]9 O0 ]# ~5 D. @1 f
   
10.     # 对左右两部分分别递归调用归并排序
    & j0 i7 s* [4 i+ l
11.     left_half = merge_sort(left_half)- y( X$ g, @2 F- U' \1 q
    
12.     right_half = merge_sort(right_half)
    . @+ I\" p  e0 z! R: K\" F0 B) e
13. 
    6 I* j5 ^8 i5 M0 Z* ]
14.     # 合并左右两部分3 _! i) L  i2 |: k! R8 m8 `
    
15.     return merge(left_half, right_half)' l4 W+ N. x7 v+ j: E; N4 F
    
16. ```1 }% D2 M* U) O9 e  W6 V* @
    
17. 
    0 h% n1 S/ s( s\" |0 _
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。% D7 X: C2 k, E4 ^9 g3 I
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   2 g5 W7 `6 f. i$ V
2.     i = j = 07 `  c7 N, j0 o* e3 D- p) E  L( L
   
3.     merged = []
   0 s3 x: y+ P1 O: d/ h\" a; c9 H% S
4. 
   2 P2 Q+ o% \1 k9 X* U( ]* F. K
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   3 }; o8 a# _: O( @  C
6.     while i < len(left_half) and j < len(right_half):: z6 j; j' h\" j7 C3 G% G: j2 _) w
   
7.         if left_half[i] < right_half[j]:
   + N7 a: O+ a4 d( q0 C
8.             merged.append(left_half[i])
   6 h$ ~3 M6 ~$ _) c4 S7 e
9.             i += 14 ]& Y6 M1 T4 ?. \5 U
   
10.         else:
      r\" z: i2 q$ K# M
11.             merged.append(right_half[j])
    / D1 s1 T+ F. J. X
12.             j += 1
    8 `3 V0 d! S. G( x' ^\" T2 i
13. 
    # r# I/ t% y! H6 L# T
14.     # 将左右两部分中剩余的元素添加到 merged 中\" I& M& f5 T; Y6 N
    
15.     merged += left_half[i:]# q( T. S& O) Z! h% W, K, b
    
16.     merged += right_half[j:]  B0 i' L) w9 Q; F8 }
    
17. 
    1 r- o$ x# z8 e
18.     return merged
    ( f9 r8 {5 j) K, X& V3 k
19. ```
    % f# P2 `4 h, x+ I
20. 1 I% V7 i4 c& K1 F
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
) X7 u7 e( ^' I. u) r" o
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
9 ?+ B6 s, x& t) L& h4 i6 e& z) {! ^
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
  b  i' I, b& N. B8 d
' X5 b$ V1 c0 Y1 I对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
, @" F9 W9 _: w, t. K; L8 q
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

; T7 r9 \: E2 V& Y6 D& i9 a: W测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]* q. c8 @4 f7 z1 Y1 V) r
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   ! H6 B$ k$ ?' y2 R/ M
2.     public static void main(String[] args) {
   5 B$ K% o0 {8 ?
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   ( M! X6 b9 ]3 ^1 |7 a, M7 J7 m: e
4.         mergeSort(arr, 0, arr.length - 1);
   ! ^2 M  H3 l% u9 M
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   ; s4 s9 g9 h6 m& e) n
6.     }' |+ q. k# |9 w3 r! C
   
7. 7 q9 u- x3 J6 A1 [; a' P
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   1 T( R# R1 }% D, @4 [) X1 e
9.         if (left >= right) {9 `0 o/ @. h1 {. l
   
10.             return;
    , H4 d5 r6 g$ {4 M7 h
11.         }
    7 `% k& s4 d1 P1 i7 m$ g8 A
12. 3 z4 e2 E\" Z' {! z
    
13.         int mid = (left + right) / 2;1 h+ A8 t\" R: j0 ~; V
    
14.         mergeSort(arr, left, mid);\" r+ I- g8 U. B) z: A: J
    
15.         mergeSort(arr, mid + 1, right);
    6 ~- J\" h: n3 t( [9 s) C: ?1 c
16.         merge(arr, left, mid, right);. `. u: s- z; W* o( L3 v
    
17.     }  r\" {- S4 y/ O' S8 I$ q& l3 E
    
18. 
    8 N/ E2 ?! ?3 ]7 i
19.     public static void merge(int[] arr, int left, int mid, int right) {7 Q8 F4 w+ _5 Y! F2 ^0 T# W
    
20.         int[] temp = new int[right - left + 1];7 z& a1 u$ z/ f6 |- D0 S
    
21.         int i = left, j = mid + 1, k = 0;
    ; y& D\" o$ r1 d% E
22. 
    2 m1 d# R8 L8 v& v# H) h- w1 S4 J/ N
23.         while (i <= mid && j <= right) {
    8 L* i6 A7 X( o3 E+ Y
24.             if (arr[i] < arr[j]) {9 X( ~/ b2 d* C- _; k  _\" S
    
25.                 temp[k++] = arr[i++];# G  m4 _) t9 E- ~+ ^4 ^. F
    
26.             } else {
    \" T4 ~% F- U+ I8 t/ V, e
27.                 temp[k++] = arr[j++];
    ( g4 r+ _0 r/ J* F! Z
28.             }
    ; M1 m8 B# n' C1 u: o5 Z
29.         }
    9 n9 R! @2 y4 s' R; }( g0 V
30. 
    ' R+ U* J* `& I7 m5 F; m, {
31.         while (i <= mid) {; e4 {3 [! w/ t+ E; x
    
32.             temp[k++] = arr[i++];
    1 w  b4 F4 K1 N+ B, Y* {( v% h% ?
33.         }8 K9 `: P. p* B, R9 s5 v. D7 W9 l
    
34. 
    $ Y) }2 }2 l8 Z, O! C\" ~: p% t
35.         while (j <= right) {% P2 A9 s! B2 L. W0 x
    
36.             temp[k++] = arr[j++];
    / Q. ~1 e1 O2 {( X  N\" K! u) u, [8 O  q
37.         }( r$ x! d\" A( J2 _/ U6 ~
    
38. 
    $ P+ S7 }. p! t. t2 Z5 ]
39.         for (int m = 0; m < temp.length; m++) {1 U% ]# ^2 i# A1 _6 Y
    
40.             arr[left + m] = temp[m];\" `  C# z+ e( z& w. X\" M% M$ e
    
41.         }
    + R$ o\" c* p2 j& j
42.     }
    $ d: x/ M' O8 U7 f$ S, r\" G
43. }

复制代码

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

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

0 @/ O+ J! [# l% k7 D" \, q8 bmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   + f; H7 k! V* A2 M
2.     if (left >= right) {
   ; t% P) `/ O. J$ X
3.         return;/ u5 @( i4 G5 J9 K6 ~  r
   
4.     }& A( Z( d' O+ V* ?4 ?
   
5. 
   6 L$ `% Q% E. F, g- j% Z
6.     int mid = (left + right) / 2;4 h9 t) G& N' _3 @1 t0 X
   
7.     mergeSort(arr, left, mid);8 K8 E\" d$ h\" ^. ~; A4 w0 u6 M4 ]
   
8.     mergeSort(arr, mid + 1, right);6 p3 U# E0 ]6 i% I$ L. ]
   
9.     merge(arr, left, mid, right);
   * d; Q( ^, m, p9 J+ a% Y. v, y
10. }
    , s$ v0 M( e1 q$ X) U
11. 
    ( B; B. P0 t9 n' P# H2 r. ~

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
% d8 p/ d6 k& n  }, S
! F9 W9 u( s4 K4 N8 d9 I! }5 \+ P3 O! F最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
3 T- A1 _- O! Q) C. {5 vmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {% e; ~  m\" |6 E9 S& R9 Y! v  [
   
2.     int[] temp = new int[right - left + 1];! ]. C4 H0 E: x2 j
   
3.     int i = left, j = mid + 1, k = 0;
   * d3 T' g9 i, Q2 i
4. ' A  j2 J5 D/ o. u3 \
   
5.     while (i <= mid && j <= right) {# F' }( W( a: p/ e
   
6.         if (arr[i] < arr[j]) {
   : I# P* F8 r+ ~
7.             temp[k++] = arr[i++];
   0 p# k/ y* C- L. B' b; R7 b- _
8.         } else {9 C% z' v$ u' v8 E5 J' K
   
9.             temp[k++] = arr[j++];& h- v+ ~4 P2 V7 @0 M1 Y  J6 [
   
10.         }
    $ _. y2 r. K; w8 J
11.     }
    1 V( W3 f4 L- B3 l\" y4 H0 M
12. 4 z1 N6 C/ j& }! [( |3 J
    
13.     while (i <= mid) {! n2 b8 G: G& X' i
    
14.         temp[k++] = arr[i++];
    6 f' ^3 `! s. E
15.     }; t8 V8 @% ~% \  @% j
    
16. 6 h7 ?, X. u) l0 t& `( @* {
    
17.     while (j <= right) {
    1 _7 F0 D8 E; |* J* ^
18.         temp[k++] = arr[j++];
    \" X# {+ c& [9 c$ e
19.     }2 r( q8 M, c: x, j' W4 P: g9 K
    
20. 
    ) p  ]4 F. H5 h6 M6 {; N7 z8 X
21.     for (int m = 0; m < temp.length; m++) {; F1 |9 _/ j) ?9 ?+ M
    
22.         arr[left + m] = temp[m];! c+ K; x% a5 `# o0 y  R
    
23.     }  n% R& c& T6 s1 M* |2 i! `
    
24. }$ L. N$ G5 \\" ~& l* G) V
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
# ~, x* w# T1 @5 @6 n4 s8 M) u
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
, W9 ?/ a$ ~. o# q' C) w; \0 O
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
6 @) U$ b" F$ H: L- `: |
2 C" \; V+ y+ K需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
9 a' _' V5 c: a/ |5 Q& ^

+ M' p% x. u& Q# d5 W- q0 w: c
# s1 R3 G- _  p

; G! V# V' h7 q) D/ M, O# q

8 i0 J% N1 w* j1 z- Z