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

2744557306

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

  z; w, r. d" E# o' M+ s) E以下是一些常见的排序算法：

" X# ~$ M8 c$ E, }" L冒泡排序（Bubble Sort）
# C! @5 }4 b( _* }# L
6 Y" Q8 e2 Z1 Z1 X& V: g% A; g插入排序（Insertion Sort）
, Y: V5 _' D" H* o& x) B1 t' P
选择排序（Selection Sort）
' G6 e4 M. Q' k; z4 i% m7 Z8 b8 S
5 \3 i. X" B) W+ B% Z归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

一、基本介绍介绍
3 v+ T* f2 V, x# r% i* i1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
+ r; R; ?6 |$ t! F% i$ ~) t& ^. ^
1 C5 }. d5 l) f, k5 q归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
; P: I$ B5 F' ]+ G
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
" h8 c  I: p- m, E8 e
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
8 Z. M; f/ O1 F& B7 z
5 P! S9 o6 T+ Y$ N合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
$ c3 {) C! r- B) J  m' q- {
" b* G8 O. a$ R定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

. M* _1 {3 M( O) H# m6 |比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
0 C3 e) l" Y2 v7 ], P+ A: H
重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
7 S! ]+ r9 v$ J6 @. S, j. h
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
! v( C: b/ H; z, Z; |; a8 ]
$ ^# e! v+ a! }( Z7 J6 V0 S1 I原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

1 h, U* Z$ M' Q0 G; Y假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
7 n0 h- A8 p& ?, M" i1 c; p
* L+ D" r7 X5 _' Q) y  ]首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

; u$ ?2 U3 \( l: _* A8 G对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
# X# N1 A; l  s6 U* k1 ?* H/ k
9 G" [+ |% j6 g& K2 R7 x将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
$ }; C$ H$ H8 i  {5 D) m
% }& x2 S9 G! o5 r因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
- Z: K# u9 k; K9 }( f+ x+ D
1.2 复杂度
4 q5 z0 D1 h! {4 s. Z5 F$ Y归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
% i+ g! W) o/ n
这个复杂度可以通过分治的思想来解释。
& A: k' F) Y; ^) A
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

" x( Y. c! o/ w: V7 ?' X每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
$ \* ?! v# ~. f9 J; J: d% O% A" `; z
8 _; B; [7 G9 x  E) _4 @+ `) i! j这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
. P; M8 F4 r5 [: ?; }0 h/ @' I" s4 a
1.3使用场景
8 j. q; y( J- B2 y9 L归并排序的应用场景比较广泛，主要适用于以下几种情况：
6 r; W$ P% P" H0 P9 e
8 S2 n' U+ W7 b5 O- V; `对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
/ Z5 j* C( d# n
! F: F  L( D7 Q2 ?9 K# C* E4 T, i对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
' a' B3 T+ c# @! \0 q
' Y" X4 l, ]# a4 S$ [4 I8 X0 N5 o对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

; u1 O2 `+ P7 Z! j8 z对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

- O. f/ e& x- J1 y7 g6 c总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

# K7 `9 m4 V! A% y( Z二、代码实现
2.1 Python 实现
* j: I, e. N4 G+ F/ t4 o6 _! z  R以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):; P/ c+ K3 q( |( r& W2 M
   
2.     if len(arr) <= 1:  _5 `0 s9 j( w' y) c
   
3.         return arr& `# [0 x  ~\" `4 V3 Y( T/ l
   
4. 6 p; l- M1 s! V  B. F
   
5.     # 将数组分成两个部分
   \" _* d* i7 [7 I3 d5 E+ n( f
6.     mid = len(arr) // 2
   ; U1 v8 v# m, J0 S
7.     left_half = arr[:mid]
   8 ]5 O$ R* G, }7 X9 O2 ~$ s8 t
8.     right_half = arr[mid:]0 |& C6 J- }$ d; \+ N3 |/ p# L+ ~+ L9 z
   
9. $ T. w3 A9 {& N0 N* d4 i6 f  j
   
10.     # 对左右两部分分别递归调用归并排序
    9 d( Q0 W7 p1 B5 \4 T7 [
11.     left_half = merge_sort(left_half)
    ( g, C; W- i  h, s* Y) W
12.     right_half = merge_sort(right_half)
    ) {# r; G) g! s- {5 [! C/ Z
13. ; K4 }! R/ ]: W) P# o
    
14.     # 合并左右两部分
    8 S  n0 _: y- E5 d# [
15.     return merge(left_half, right_half)
    5 x8 m- n, ~; y. y+ [
16. $ c* k6 U( {6 d0 K
    
17. def merge(left_half, right_half):
    & H7 N. x2 Q# }  `1 {, c! C
18.     i = j = 0+ k- ~% W/ o\" {+ a7 f; @. s
    
19.     merged = []
    0 C  W  T9 }% P1 d2 ?
20. $ k5 n5 w3 s$ u; z\" h9 s
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    ( X+ D7 ^2 G6 p4 w
22.     while i < len(left_half) and j < len(right_half):1 w& h3 P  O3 k* q; E2 O& n
    
23.         if left_half[i] < right_half[j]:
    % ?\" F; x4 v9 H* c- ~
24.             merged.append(left_half[i])
    0 {/ T: Y7 h: G/ K1 n- m6 {8 w
25.             i += 1! o( J; Y8 N9 |* h9 n) @+ Y7 J
    
26.         else:# U9 `' ~' X8 s& V6 G/ j
    
27.             merged.append(right_half[j]). u8 P4 y' S0 [7 {7 X  a0 r; m
    
28.             j += 1; F; x' f4 T( ^6 p1 c
    
29. 
    * a: `6 u/ W8 p$ T
30.     # 将左右两部分中剩余的元素添加到 merged 中
      r* \% s8 }, E# a7 g! _% c4 f$ ?
31.     merged += left_half[i:]$ K4 S8 Y- q' t\" ?\" n4 ~; j
    
32.     merged += right_half[j:]& p% |: O( T5 S( c: {* g
    
33. ! s! h- G# W0 v4 ^+ W  F& Y4 @7 f! A
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   9 K  S7 N- P4 `\" I. V
2.     if len(arr) <= 1:
   + ^. S& d, v7 A! D' x; z
3.         return arr$ D% K; s* F& O6 r
   
4. 
   : U, A, K6 I2 c3 [# S
5.     # 将数组分成两个部分
   ! ]. Z+ T- q5 K$ h2 R- ?/ G
6.     mid = len(arr) // 2
   5 ~; r0 f0 x- {
7.     left_half = arr[:mid]
   , i/ ]0 Y. ^: V6 L, ?# D! D8 i
8.     right_half = arr[mid:]
   * f$ P1 n8 ?. E) ]
9. 
   % q9 [) Q, `$ q\" M3 R- a
10.     # 对左右两部分分别递归调用归并排序$ r$ T4 Q& {; @1 U\" C+ ]
    
11.     left_half = merge_sort(left_half)2 n& j0 t( t7 P8 c1 Q
    
12.     right_half = merge_sort(right_half)
    7 f( C- c( G7 R, l( L/ M
13. % O6 A# b* r+ K- B2 |
    
14.     # 合并左右两部分
    0 G/ k2 u% C\" ]
15.     return merge(left_half, right_half)3 V6 x9 O( M& m% D0 i\" n+ [1 x
    
16. ```9 a$ C: |% L. l+ l
    
17. . j0 c( O% s# n# V/ G# Y5 \1 Y
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    . y# _7 w3 B8 z* @# V

复制代码

merge() 函数

1. def merge(left_half, right_half):2 K$ r9 @; c5 w
   
2.     i = j = 04 Y' U+ j8 j+ X7 o$ q4 O
   
3.     merged = []' g% R9 h9 p& e+ t; p, @! R8 x
   
4. & Z6 I) N! f8 v5 u0 C
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   ! j0 d1 Q3 G  z% P0 b9 k
6.     while i < len(left_half) and j < len(right_half):
   ' Y& {\" r\" l+ B$ S; S# k
7.         if left_half[i] < right_half[j]:1 _* x# J8 a0 D& l5 p
   
8.             merged.append(left_half[i])$ v* p( W1 S5 B. X8 K
   
9.             i += 1% J$ F5 X) P9 b8 `, \
   
10.         else:' U# r: h2 L\" q8 L1 C6 f, ^/ t
    
11.             merged.append(right_half[j])
    0 R9 a. y- \* k
12.             j += 1
    \" z8 d0 N3 i( }1 b
13. 
    - O+ P, s- c4 a
14.     # 将左右两部分中剩余的元素添加到 merged 中5 I' D0 J: C8 z: j+ M1 |
    
15.     merged += left_half[i:]+ }$ V\" P! T4 y7 D3 T; x9 \
    
16.     merged += right_half[j:], u2 B* D0 C8 Q. Z+ W
    
17. + x7 e: P; H2 I9 y
    
18.     return merged
      z( V4 ~9 @$ ?4 H+ V
19. ```
    ! m' |% X  V3 n! e3 y7 h
20. 
    + D0 p2 u  Q5 ?8 y! r/ ^4 {, X+ z7 g
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
0 g: N1 h4 k' ]
" R0 O" X% z. y5 m判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

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

: ^3 H- t( x! t$ _3 y) I3 J4 b对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
1 E3 a  E) V! _; G+ F- r! N
# R1 {: G; Q3 J4 q* G( Q+ I' G合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
, A# T* e2 W! j8 ^2 x5 \" y
测试
9 R0 t) j( j  y" o$ ^; V在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   7 H; S7 k* g- v- S; y' B3 O( M
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

1. public class MergeSort {
   ) P. ?* `: [7 I. T# L
2.     public static void main(String[] args) {$ N/ C6 q  o& Q
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   ; D( P$ v5 D6 J9 G4 }
4.         mergeSort(arr, 0, arr.length - 1);
   & F8 }% n3 S5 N; y! X
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]% n7 O, h4 A9 X2 Z3 b% {
   
6.     }* {, U% M! w, a! B* \
   
7. 
   0 |& D# e3 I, s1 T9 S( O8 L$ u
8.     public static void mergeSort(int[] arr, int left, int right) {
   ; H3 |! A3 ~5 r* a- w' n  u
9.         if (left >= right) {1 W/ X! A8 G( G- ]7 ]' M0 D
   
10.             return;
    / B- j* ^1 M; g& P
11.         }/ a\" {4 u7 G/ x5 p8 h; _7 R
    
12. ! N5 A  R! L6 F$ ]
    
13.         int mid = (left + right) / 2;
    : L3 b6 z% `- T; U1 W$ Z$ X2 j7 _
14.         mergeSort(arr, left, mid);2 M/ X0 o/ f5 @
    
15.         mergeSort(arr, mid + 1, right);
    6 _1 L5 `2 `4 U0 F$ y7 N# j
16.         merge(arr, left, mid, right);7 K, y1 y+ b! N2 F2 ]$ j
    
17.     }
    4 t1 C. [& M' q: {+ O1 N$ t
18. $ |. p2 v& o( v# w6 x) v: Y; h) H
    
19.     public static void merge(int[] arr, int left, int mid, int right) {1 g8 V7 s. f+ Z\" y) K
    
20.         int[] temp = new int[right - left + 1];/ ^\" Y- D) O% `; T& O% b
    
21.         int i = left, j = mid + 1, k = 0;4 w4 I& @1 u# s
    
22. 5 B, m) E4 o( y
    
23.         while (i <= mid && j <= right) {) W: |6 r8 |* W8 Y9 ?4 W4 S
    
24.             if (arr[i] < arr[j]) {
    : J& M/ j/ T. M. g3 f\" J' b* Y
25.                 temp[k++] = arr[i++];
    9 |1 J. }7 t2 B: _- \' |  }
26.             } else {
    6 f4 \7 j6 u2 c, \
27.                 temp[k++] = arr[j++];
    $ l  z8 q7 w5 x/ ~% T4 Q) @+ P
28.             }3 ~: r$ t6 q1 Y  J8 v; ~
    
29.         }
      i\" j9 J1 [0 v/ H8 ]8 V- H
30. 
    - h+ q: {3 e) q8 K. {7 T' d  D. z
31.         while (i <= mid) {+ C: V( I3 ?, ]) K7 Y/ {
    
32.             temp[k++] = arr[i++];
    9 {' o4 j6 r! p/ I
33.         }
    ' K* s# R9 g$ i, {
34. 
    5 j; E8 d& y* V! m& H7 N
35.         while (j <= right) {
    ! M3 q  M, Q  [- m+ k' A
36.             temp[k++] = arr[j++];8 D8 S, i; v\" S( y! U8 ^* I  k' Y
    
37.         }; N2 [. U* F6 Z% h: A
    
38. 
    & d0 s! ]* Y* K: h2 u+ j
39.         for (int m = 0; m < temp.length; m++) {5 G) k/ h$ d+ J' o# X! P9 i
    
40.             arr[left + m] = temp[m];7 J5 Q, V; q& I\" m- L
    
41.         }- o+ R+ z5 Q/ a  k0 P. V
    
42.     }7 G: d& E' p1 K/ a8 c: N: z
    
43. }

复制代码

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

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

2 Y. I$ Q9 h3 e/ x2 e7 g/ M5 w2 X/ xmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   : q4 k' O$ M5 A9 \: L. b4 E
2.     if (left >= right) {3 B( n8 \; \% @6 H- y& y
   
3.         return;- ^: Y& P( C* f\" ]  _
   
4.     }; K4 u+ ^. s% T$ e/ b; c
   
5. 
   ' x  ?6 t\" k1 G2 V
6.     int mid = (left + right) / 2;
   : P' d& Z' T$ a! u
7.     mergeSort(arr, left, mid);
   + H  ]0 Q# ?. L9 t8 {; L* {, i, y
8.     mergeSort(arr, mid + 1, right);1 w# {% P% J; F; I# I0 w! Q1 e( A+ ~. y
   
9.     merge(arr, left, mid, right);  M: R) v) G7 A  O% Y, u9 V
   
10. }( N! Q: x* w3 U. R( t# G5 [
    
11. 
    # m) u7 e, l1 l/ t8 k

复制代码

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

7 A( p" ~: w2 D% ]% F/ Z  {- {对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {
   ' s( A  b( s- ]) X' Z; e0 I
2.     int[] temp = new int[right - left + 1];6 l9 {: i1 I1 m+ X9 |  j- T3 R5 y2 n
   
3.     int i = left, j = mid + 1, k = 0;
   3 S: `2 o3 R. X3 \) D
4. 
   4 I6 @+ D) r% }7 B
5.     while (i <= mid && j <= right) {
   / v0 U* H& u4 L! n$ G) s
6.         if (arr[i] < arr[j]) {1 R0 _9 W4 V. F' l
   
7.             temp[k++] = arr[i++];8 \- `# I1 d1 A) K\" ?+ p
   
8.         } else {
   ( c' i2 v& f( i/ u
9.             temp[k++] = arr[j++];
   , i2 Q\" v3 G; {8 L- y% r, K
10.         }6 @6 T) A& A/ y
    
11.     }$ t/ P: d, V4 M* I
    
12. 
    - c' X' o, W\" p  J  S
13.     while (i <= mid) {( ?: W) D3 p3 _, ~! V
    
14.         temp[k++] = arr[i++];
    & i9 ^8 @! v( |# G5 i9 F% |
15.     }
    ) n  \+ _% E. t. C\" ^& M8 k3 z
16. & k( u8 N- n) q+ S- k\" Y8 T
    
17.     while (j <= right) {* b! i! k/ O+ B: X- ?\" p. z& {' _
    
18.         temp[k++] = arr[j++];
    / ~: S9 G5 o* c' U3 B; P
19.     }
    1 g2 x% Y3 {  F; |5 Q- U
20. 
    3 v+ t4 M* p- }6 i- j  X
21.     for (int m = 0; m < temp.length; m++) {2 ?: z6 Y7 h$ H7 _- }% }0 k$ i
    
22.         arr[left + m] = temp[m];# e- ~\" K: t7 T  ]: _
    
23.     }$ O: c- g, b1 Y3 H7 z( a/ {
    
24. }' x9 B7 d) P0 z* G( g. p, q
    

复制代码

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

9 D! l2 M/ H! F9 a" p" \0 p合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
# q$ q- n+ B" E# J& P# C
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
- W; b: U/ B" ~  ]' [/ z: a0 u
+ g& J4 ~5 e1 y; H需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

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



, p3 g3 {: g, g2 A3 T, b) Z

: C/ R" C; b. v