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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
* C- [! G" n( h5 D- ]4 g1 ^# m
以下是一些常见的排序算法：
& M" q; V+ T" a9 G2 n
" @9 u; ~$ z. T/ _4 a$ d冒泡排序（Bubble Sort）
1 p" @7 K$ `' z! I) P
+ {7 ^' g' }0 L8 N插入排序（Insertion Sort）
% e7 r  t2 }6 u1 E4 B
" \% ], ~9 V# Y9 ]5 x5 Y选择排序（Selection Sort）

5 q5 Z0 h3 Z- p: C( L5 q% V" Z1 O2 F归并排序（Merge Sort）

快速排序（Quick Sort）
; ^& Z$ w( O5 g% ^7 {. A
堆排序（Heap Sort）

' z7 F, B7 H2 x5 L. D* E2 `* u一、基本介绍介绍
1.1 原理介绍
" p4 b5 I$ `) I" O; g归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
0 m3 P, _! X# _* z, }8 S3 H, _0 {
0 ~! i+ A* l$ A4 ~归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
" M' b7 I6 A" l0 Q! v0 P& x* ?
/ M0 [) l# y+ Z! c! Y6 o分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
* T0 t9 e2 q- i7 w( f; T+ H
- m; M5 _# ~1 ^, k2 v合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
+ X* ^2 p3 _0 M2 _
- |/ V1 A9 {3 |定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
( O7 N. z3 I1 Y
4 h" s  {. f3 C# Z重复步骤 2，直到其中一个数组的元素全部放入 C 中。
  M% \/ A# s$ m# r
将另一个数组中剩余的元素放入 C 中。
! w$ G% k; s( |6 l3 W
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

; S4 N, R% {* v2 r5 I首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
# r5 d9 ^2 J" P% f& e1 C0 r
" `! M# n6 l' H; E* k对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
+ q3 T. ^5 m3 U3 O) M! T
. T9 ~( V! `' `+ q4 J1 l对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
$ B' ?. ?. _# N1 o8 j( g* D& h2 J1 Q$ y
5 q- w% L: m+ R2 P接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
6 \# C% ?. ?2 A- _) ]
& ~, F* {! _; j因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
; v2 L5 R7 u, O0 Y
1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
# u* }2 ~, w3 G0 X7 T: Z; ^
" L, e: p* Y& U( A$ ~) R这个复杂度可以通过分治的思想来解释。
# R0 R! [1 T9 Y
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
0 u: D. G* d3 d: y
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

) Q, m& u: n/ H- _6 ]归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
/ ~5 X6 [( s9 d& u2 [
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

* Z' V& k1 t3 d& h对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
7 X. l; Y2 ~! p
1 W1 [9 `) K) |对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
; K/ T  p( O  s+ j' Q4 h
' f7 s7 l# s* Y( ~1 _6 q8 h7 a对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
& n+ L/ I  ~' r: @/ e& h
- c* t6 M; [9 n4 T( @对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

' }7 a5 {) s; X6 s4 T) t" i总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
2 t8 V+ t5 Z. P8 R
二、代码实现
) z6 q1 C6 o1 |2.1 Python 实现
( `, y7 T) p7 T( q; t以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   . S7 [' c( P- _% _) X+ f6 a
2.     if len(arr) <= 1:
   $ c3 d6 i1 a$ n# M
3.         return arr. F+ |  |0 z1 E# n
   
4. 
   * d9 X: a* J5 k  _) T
5.     # 将数组分成两个部分
   , ?8 h* x$ {) \% @( n; X6 S
6.     mid = len(arr) // 26 _) Z; v9 V7 K# o5 b% M
   
7.     left_half = arr[:mid]) `% f0 w& s9 N2 T; |% H) ], w
   
8.     right_half = arr[mid:]5 v$ T/ z4 D7 P# T6 b( R, n5 ]
   
9. 0 V- H! K+ G6 _) z1 Q7 X7 L
   
10.     # 对左右两部分分别递归调用归并排序* P. H2 V5 ^# u9 B$ E
    
11.     left_half = merge_sort(left_half)! G7 e- H& T' b* A
    
12.     right_half = merge_sort(right_half)4 ]6 }! g% Q7 M; ^' [
    
13. 
    ' L1 J3 d, m2 E
14.     # 合并左右两部分
    - p( L) p/ r( i( L; h+ a
15.     return merge(left_half, right_half)
    % b6 N+ B1 i8 |- j( ?! ^+ v! f
16. 
    # y& A7 S3 K# [6 J
17. def merge(left_half, right_half):- e' S9 C7 ?1 \6 E- }4 g: W, g
    
18.     i = j = 0
    ) X  D, `) B+ r( k8 m3 J# U
19.     merged = []
    - Z0 l' r5 A1 d4 j
20. 
    : u2 T* g\" n6 ]0 a- g
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中  x& L$ ^2 l8 ^$ I- v5 l
    
22.     while i < len(left_half) and j < len(right_half):
    ' y- [: e# [' Z% |\" E6 X
23.         if left_half[i] < right_half[j]:$ n$ a7 T\" d* k& m0 C0 f
    
24.             merged.append(left_half[i])' T! g& O- D7 ]& F2 {
    
25.             i += 12 u, L- K/ u9 P5 w: a
    
26.         else:8 j4 [2 b4 ?+ v. T
    
27.             merged.append(right_half[j])8 F0 A2 H$ s  B1 x3 R3 S7 s% k
    
28.             j += 1/ c+ F. C2 L' x% [
    
29. ( [; p6 A9 d- ^1 a
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    - |2 ?9 K\" O# U/ r6 M
31.     merged += left_half[i:]\" E/ f$ s$ ?( r! I2 M* b
    
32.     merged += right_half[j:]! q* X. C1 t( L! n4 x; ~
    
33. 
    . ]' D% @6 E+ c; M; d
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):+ P. u3 W0 L  R
   
2.     if len(arr) <= 1:
   $ I7 c1 I( t8 D
3.         return arr) m( e  |! X5 Z% H
   
4. 0 u! {& e; o* e2 ^: l
   
5.     # 将数组分成两个部分. b$ s4 O) H- y6 z* ~/ a! Q
   
6.     mid = len(arr) // 2
   ! `- R0 r4 [9 w, ?  l  e
7.     left_half = arr[:mid]
   \" }( x; i; O; S- Y! C
8.     right_half = arr[mid:]. i  z+ m9 l# i5 c: r; ~
   
9. - Z9 ^8 q) l6 j  ^- J! Y, Y
   
10.     # 对左右两部分分别递归调用归并排序
    ( C4 k. j) X\" g6 ], N! ~8 I. J% h/ Z
11.     left_half = merge_sort(left_half)+ I4 W+ L8 S+ ]4 [% n
    
12.     right_half = merge_sort(right_half)
    & j  M4 m1 U4 J0 j8 ], C7 m0 k- L
13.   s\" L! I6 n& [( {9 A# T1 u8 t$ q
    
14.     # 合并左右两部分
    ) K: X+ J# r5 _: u
15.     return merge(left_half, right_half)
    , }7 \  j' q* }1 n\" Y( u
16. ```) m7 Y\" o* L! |
    
17. 
    9 z1 }$ h) [+ P# `& v, D3 ?
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。5 ?\" Y7 r* P- s$ V7 b/ w
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   $ v+ s7 \# j0 |# ~% v2 Z% l8 j9 a; Y% W
2.     i = j = 0) Q- y- ?+ s  F# @- @- A6 O
   
3.     merged = []: |6 u+ {% ^, Z: x6 G; S  y
   
4. + l0 d. U7 W- a# {0 m3 S
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中# s' w: C5 T( v
   
6.     while i < len(left_half) and j < len(right_half):
   6 d0 c1 d2 R% P
7.         if left_half[i] < right_half[j]:
   0 b' P+ w2 F2 ]) @9 L: r\" m  ^
8.             merged.append(left_half[i])
   3 C. X% z7 r+ u6 u5 L+ R/ ~( A( z2 }- a
9.             i += 1! G3 g4 \( C% J\" m/ K+ P. m5 H
   
10.         else:
    , v' h+ s- m) y+ [) c
11.             merged.append(right_half[j])
    \" p' U9 n) N' v9 ~4 Y8 _9 C
12.             j += 19 Z% n/ P$ Z0 m5 s6 O6 D
    
13. 
    0 w3 r, v) z# n\" i- }2 K% o) r
14.     # 将左右两部分中剩余的元素添加到 merged 中4 \$ r5 F( q8 d1 e. @, b5 c) P6 G) L, |
    
15.     merged += left_half[i:]
    \" a* r7 K6 R; z8 k& Y: g
16.     merged += right_half[j:]% G0 q: p5 R7 D! O, K
    
17. 
    8 t: ^# R  w# |' W* n5 g
18.     return merged% t) x5 a: y2 k
    
19. ```
    ( s) \0 f9 k4 y$ e6 g6 F2 ^% s, \
20. 7 c+ ^! O$ ~& Q7 i
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
( j  N+ {: x* J! ?- j, h
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

' C& H4 P) D% E$ [% s7 i将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

3 T1 I0 y2 R2 {  ?& U( D  C对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
3 b( ?( R/ t' G5 W
测试
1 Y2 A+ y" ^+ O/ e' Q在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   0 Q+ I7 D) y/ o8 S# L
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 {) \8 R9 d' Q9 W: ^8 j  `
   
2.     public static void main(String[] args) {. b6 o1 W# x+ k6 B# G/ z8 `
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};, w9 i% V) \/ }$ L
   
4.         mergeSort(arr, 0, arr.length - 1);, s: U4 |6 j; s! v9 ]7 C
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
     I9 `- ~+ g9 _# q/ E5 v# E( b
6.     }\" u' F# m$ N) K4 `/ L, g3 k; s
   
7. 
   % Y\" X& q: t) ]2 K
8.     public static void mergeSort(int[] arr, int left, int right) {
   # Z. ~% n6 y2 c\" l* R5 U
9.         if (left >= right) {5 t( ?( [6 X0 g% d0 n
   
10.             return;
    0 I% a9 Z7 }0 {: n0 C9 G$ T
11.         }
    \" j  b& W* Z9 {+ k% a
12. 
    2 z4 \! S# i0 _
13.         int mid = (left + right) / 2;
    4 x9 `. ~+ S- l2 c& D
14.         mergeSort(arr, left, mid);  {1 q+ S# r* H\" K
    
15.         mergeSort(arr, mid + 1, right);
    , r' N4 E) Z( U( `5 ?+ t
16.         merge(arr, left, mid, right);
    $ u6 H6 b. E4 b/ f- ~5 B7 A' Z5 \# O
17.     }
    $ d' K2 b  s( d# I& ]
18. 
    7 i( C/ }: f- z7 p6 `6 W
19.     public static void merge(int[] arr, int left, int mid, int right) {
    \" T: o& l7 d& v' S- W* b8 s
20.         int[] temp = new int[right - left + 1];  d5 e$ }$ A# Y! O  j& @* o$ Q
    
21.         int i = left, j = mid + 1, k = 0;) c2 e6 G\" m9 C. t9 L0 m# ^  ?$ o
    
22. & w) Y+ q; K' |% I8 P5 f
    
23.         while (i <= mid && j <= right) {% m& l9 t! [9 k- {3 R) l
    
24.             if (arr[i] < arr[j]) {1 d; q% b3 F\" T: d% h1 ~
    
25.                 temp[k++] = arr[i++];5 u2 k; M3 b# B+ w& L$ Q) t
    
26.             } else {
    : L+ D+ _6 b& k- Y  t0 D0 n# X
27.                 temp[k++] = arr[j++];( E+ V) |+ P6 `& i
    
28.             }& R% g! b% Z\" w8 g+ N, A$ l( w6 L
    
29.         }
    * `! S- m9 s. j9 \
30. 
    + [9 t) s# I5 E5 C- F
31.         while (i <= mid) {
    + b, @- m4 I\" X3 a: ?, B% X
32.             temp[k++] = arr[i++];  k5 O\" ?+ h9 Q$ q
    
33.         }3 r, E- Y2 I3 K\" c
    
34. 
    . g8 C( s1 B# S
35.         while (j <= right) {; P3 M. C: o! m- J. n/ b( [, U3 B
    
36.             temp[k++] = arr[j++];3 a0 f6 f* n2 L, f: |1 U$ g6 C3 }) }
    
37.         }6 S( b\" J& d7 `  {$ l8 E8 w9 J5 L
    
38. 
    - ]\" N6 V\" Q. O  e) x
39.         for (int m = 0; m < temp.length; m++) {
    / V0 b: t5 e# R  [. ?
40.             arr[left + m] = temp[m];9 G5 ^/ G! d) c\" P, R) `
    
41.         }
    \" s( T- K/ Y& ^4 S: r% R& |$ G
42.     }
    2 t8 m; u7 G6 Z3 m% i) q: n+ t
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {; Q; Y; k5 E- E' ?2 N
   
2.     if (left >= right) {
   ) r1 f2 V6 B2 r* k! l  I+ R
3.         return;
   % F\" L8 b) N: o) X
4.     }
   : k+ H& d# ~8 c0 s- r
5. 9 Y1 d  X; B$ k2 q$ x. s
   
6.     int mid = (left + right) / 2;5 e' a' Q( S( V$ _3 s: A
   
7.     mergeSort(arr, left, mid);
   7 i. Y+ _. Z\" q9 {
8.     mergeSort(arr, mid + 1, right);
   & w8 @* r% L: M6 L' p/ f
9.     merge(arr, left, mid, right);1 ~- ]1 A; I6 r\" l& V+ d9 X
   
10. }
    ( u8 {! s: F0 C% I  u) X
11. 
    / d5 L0 C8 M: K6 X; K

复制代码

这个函数使用递归的方式对数组进行排序。
" h- b0 h4 J+ ~% X1 J9 U, j- j; A: ~
9 ?- M9 K! u- z' W, z* \- ^对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
/ U/ v; a( {+ D: h4 J
( T% B- E- F$ l6 J最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {/ j0 m\" v2 q) E4 ~8 c1 q
   
2.     int[] temp = new int[right - left + 1];, g5 S$ I$ i* J2 h( j0 F/ Y9 U
   
3.     int i = left, j = mid + 1, k = 0;0 l* P* U$ Y& S
   
4. ( a( s. h* J% G/ O7 @/ W
   
5.     while (i <= mid && j <= right) {
   0 ^- Y6 j2 G\" |7 X7 H
6.         if (arr[i] < arr[j]) {1 |, o$ X' C4 _; i% n* l; w
   
7.             temp[k++] = arr[i++];4 f; x( L1 l6 M; B# M$ y
   
8.         } else {
   2 u  a$ U' S; Q# e) |1 ~
9.             temp[k++] = arr[j++];7 B4 m; ~) G9 \/ q3 s
   
10.         }
    : B2 T# l+ I: e9 L
11.     }2 D- u7 N5 q, ]* P4 a( l; V9 Z  Z# v
    
12. ) ?- M- P; `\" a& k. p5 ?
    
13.     while (i <= mid) {
    & |2 |9 `* \: H2 T' \, U- O, I
14.         temp[k++] = arr[i++];
    $ E8 @# a& g2 G3 A# r
15.     }. E# N( H% M( a/ x6 [! B
    
16. 4 J' n( ~  |2 h2 s. R0 v4 l
    
17.     while (j <= right) {( ^) T0 _  a& g: I' V0 b8 p
    
18.         temp[k++] = arr[j++];7 M, C) P; L9 I2 n
    
19.     }8 H5 T2 C5 S# h, u. [2 _6 e( g
    
20. 
    6 t' E4 \7 p( N0 _3 z$ }! x
21.     for (int m = 0; m < temp.length; m++) {
    $ }& \6 Y; }. `! g, B& V
22.         arr[left + m] = temp[m];+ Q& m2 F1 s; J7 m* J! B
    
23.     }
    2 i5 k3 Y: J, r
24. }
    4 O& z% ?\" c$ O7 @$ U9 G

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
6 I! P9 o7 x0 I! g) T7 _* ?
7 G& [3 F1 X  D合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

5 T9 k; ~% K% ]& [( K5 Q最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

6 V; H* b) x1 t# n7 }5 E+ c! W需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
: o/ J0 M! L2 j2 I  c; V7 @
9 I* T. D) G2 W  O( U/ m


" o- b  E4 N1 I! D/ {