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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
% v( G# j# H' v' Y
以下是一些常见的排序算法：
! t) W! K% y* A: `
9 Z+ p4 w+ V& {冒泡排序（Bubble Sort）

, N: v9 h: b; v# J  w0 `插入排序（Insertion Sort）
) M) A( d7 S4 c, p
选择排序（Selection Sort）

归并排序（Merge Sort）

6 V! c3 C$ P+ Y* R6 Y) }快速排序（Quick Sort）

- z) a: e, N4 ^. N, S8 F堆排序（Heap Sort）

9 j8 q3 k1 v# w3 C2 R6 Y一、基本介绍介绍
0 B4 j6 V5 E  L) C6 W3 ~$ Q0 _+ a1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
+ c8 p# Z/ a3 C6 v9 u6 I, f
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

) _. A; q, r; H* [$ x/ Y0 o分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
2 O) c# X) R! s! d7 k. u0 l/ O
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
; l1 g4 S0 ?7 ?& J) ~. r
5 [- l2 Z/ Q; V* S比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
6 p0 z0 \1 T4 M" n( G
重复步骤 2，直到其中一个数组的元素全部放入 C 中。

* T& [( D2 B: N# ?. p& q将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
/ o* `2 T+ x7 q; Q* u  x+ ]
原理简单示例
) k; V: h' |% f! a2 k& e0 y以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

1 {. `3 `4 t" n; y5 D' a; o! n+ m首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
/ I# O9 ?9 h0 ~, f% t
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
+ u: D% f# r3 y( h2 k
0 N* Z' ?9 r+ J7 N) d" g% t# N对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
' I7 z: B, q3 a! ^! V: \
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

9 J* T7 d. t$ g( e0 ]3 f- W将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

& y6 [! C3 g* X  A: d1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
) E' N. O$ e' Y" e2 o/ U- h, A
这个复杂度可以通过分治的思想来解释。
+ t+ k# u& u' d: n3 l
0 s" |6 M/ _$ C) n1 z8 P9 _首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
" V, `3 t6 P/ l$ n) Y4 {
# \3 S2 W1 r$ B每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
: q  ?: ?7 `% t5 B. f  ~/ `3 E% o# K% Y
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

7 W$ _& x. `5 ~& K$ j) Z  x对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
2 k; U+ u. A+ Q0 _$ ~% j: u
9 r% g5 h% }, ~对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

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

" i& R6 W$ E* E对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
6 v8 x/ q. _8 }" T! t4 R
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

) `' I8 T0 b8 Z9 ?& i, f. N, d( D- q二、代码实现
) {  c! W; h$ e3 z$ a: J$ q2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   7 l, ^4 D: i. L) N2 K. {* z
2.     if len(arr) <= 1:) l+ M9 D8 \8 a& B8 O) ~
   
3.         return arr. p1 s: k6 T\" G
   
4. 
     v# x# V( d6 j2 p
5.     # 将数组分成两个部分
   # m/ X0 w2 O1 Z7 V' W
6.     mid = len(arr) // 2\" Z1 v9 ~0 R\" T
   
7.     left_half = arr[:mid]
   - O8 i; W2 E1 a0 p9 J! v
8.     right_half = arr[mid:]
   8 q  `; M3 g  g/ u0 W
9. 
   ) k& a- f  a( O/ v
10.     # 对左右两部分分别递归调用归并排序6 v3 q7 `- m1 |. m3 k  [% `' {
    
11.     left_half = merge_sort(left_half)
      J3 m\" F\" Z8 @$ j
12.     right_half = merge_sort(right_half)3 y% N7 ?; J1 N( g. j
    
13. - E8 Y- R9 Q+ I
    
14.     # 合并左右两部分
    + p. v, c, C; C. m
15.     return merge(left_half, right_half)+ Q! b4 P8 p2 a6 `& B
    
16. 
    % B5 @6 I! R8 }* j% k- X+ F- }& x; r
17. def merge(left_half, right_half):
    1 L/ R- ?/ Z8 `
18.     i = j = 07 ?8 D0 j* s% P8 ~\" Q) k# X
    
19.     merged = []# ?, l& w/ y5 N7 {) U
    
20. % d5 l6 o/ c5 E, Q& L\" l) N, Q% S1 b+ f
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    % Y5 J# H% Q8 \* a5 m2 |4 M% m
22.     while i < len(left_half) and j < len(right_half):4 E9 [/ z% n1 Y! P/ x
    
23.         if left_half[i] < right_half[j]:
    . p$ }' _3 S& b) c+ h, g' {
24.             merged.append(left_half[i])
    4 B5 e5 l% j2 A, y7 f' H+ Q: A
25.             i += 1
    # |- u6 }1 X* i$ ?9 x2 S
26.         else:' p  Y, @9 m) a
    
27.             merged.append(right_half[j])
    / v& N- v: ?3 `$ s( E/ @
28.             j += 18 o# O8 v6 Y. E8 a' a+ y
    
29. 
    $ L3 N+ Z, W! M
30.     # 将左右两部分中剩余的元素添加到 merged 中3 `. i# l: q: U% }0 Y4 x- u
    
31.     merged += left_half[i:]: V, j- ?  b! C* [; }
    
32.     merged += right_half[j:]
    % O, V# q# W2 \4 P
33. 
    6 W9 C+ T8 w6 f3 L
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   , j3 d& D3 n9 d! f3 `& v% t
2.     if len(arr) <= 1:
   * h4 m% P* o. i$ ~# U
3.         return arr5 q0 }8 V: S+ |' {5 {
   
4. 
   - m% s* h* H: ?
5.     # 将数组分成两个部分
   ' n: e/ X1 r\" L% C3 s# v. {; ^
6.     mid = len(arr) // 2+ E% C7 |$ O9 F/ z5 ~  N3 b1 j
   
7.     left_half = arr[:mid]% ?; N! e0 u1 ?1 G/ I- c
   
8.     right_half = arr[mid:]
   $ a* ^' `5 V9 \8 F9 G\" J) ]
9. 5 X- v; i% g; S+ z- O) i
   
10.     # 对左右两部分分别递归调用归并排序$ C4 _% Z1 x- H( L
    
11.     left_half = merge_sort(left_half)
    + g: B6 o1 s. w4 p1 _6 T
12.     right_half = merge_sort(right_half)
    . y' k% _/ Z3 r
13. 
    8 @) l8 a; C( ^7 P/ i2 e
14.     # 合并左右两部分  g: {; E8 O! H% s
    
15.     return merge(left_half, right_half)9 |7 U; y5 v0 w
    
16. ```
    6 \$ z% T+ T\" G7 G/ R  G! Q2 @
17. 
    5 f5 u+ j, m$ @. c6 q* j9 p
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。& t/ Z) f\" y9 O3 C' w4 U( P( L- r7 \$ m
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   8 h; l3 R: ^  t; b$ @8 x0 k  x
2.     i = j = 05 ~/ L4 ?. G4 p
   
3.     merged = []
   - ~8 T& H3 [5 G' ^: A
4. 
   ! n# n4 n9 f& T& O
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中/ E# ]0 \% |! b, j0 B; M
   
6.     while i < len(left_half) and j < len(right_half):
   $ t: E0 v7 r) u0 s\" z, A
7.         if left_half[i] < right_half[j]:
   - }, Q' U/ {( Q( ?' ^' T
8.             merged.append(left_half[i])
   . D4 F\" M4 H. \
9.             i += 1
   ) ]( K; f5 P% r* J- G& _( D. X# o- n
10.         else:
    ( f# P  P; G2 e5 ]2 k% h3 @
11.             merged.append(right_half[j])& l\" z. w) j! `: A* Y* P\" D  Y
    
12.             j += 1
    # J4 N9 X( s3 t1 @
13. 
    9 l7 l3 \2 f6 c- C
14.     # 将左右两部分中剩余的元素添加到 merged 中
    / i# d1 U7 D: T$ N1 x
15.     merged += left_half[i:]4 T% d\" l' _3 l
    
16.     merged += right_half[j:]7 R) ~1 j6 F% d' K# y# P! q
    
17. # ~& _\" e+ q$ b# a5 b+ T% Z8 ]
    
18.     return merged
    : J8 Y4 u; V/ E$ G* ^
19. ```
    ! n7 O; H$ y+ O! m, T) c! c
20. 
    - ?. E5 i4 n5 V- v( ^& l
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：

: T- f: a6 j6 x7 C6 N2 l判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

6 _- n0 p4 {# K9 k0 @' e) V* m将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
: ]$ a! E, L; Z; I: J/ a
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
2 w- r, L$ q% c5 v0 n6 ?4 C
: P* k0 X) R' C! R3 r6 K0 A测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   % d& {' [( a\" q4 @& ~\" c
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
8 D: [$ m# |/ w/ ?/ t1 B% F9 x$ `! B2.2Java实现

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

1. public class MergeSort {# D\" a2 G; e$ ^5 s
   
2.     public static void main(String[] args) {
   2 e. y3 H1 H9 Q
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   & C$ R+ Y$ H* H) t\" u
4.         mergeSort(arr, 0, arr.length - 1);. Y& c# }+ S0 u2 I# n
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]' D6 x. y  d) z) o% t
   
6.     }( }+ D6 A' Z# Y/ o# _6 Q$ g% m7 G
   
7. 
   + S. p+ B$ ^5 W. E' R. [8 b; m4 J
8.     public static void mergeSort(int[] arr, int left, int right) {
   3 ~$ a) U' Z3 b
9.         if (left >= right) {
   # a& n- d3 U+ A5 y  z+ X4 u\" y
10.             return;. g0 u3 h( r  L\" _2 C
    
11.         }4 [: r1 f) z/ T& X0 u  `- H\" L
    
12. 
    6 I, _; M' J8 M8 s
13.         int mid = (left + right) / 2;' g+ F/ A$ M$ N/ ^
    
14.         mergeSort(arr, left, mid);
    8 R  K9 F\" d5 R! [
15.         mergeSort(arr, mid + 1, right);2 p( X5 J* q: r$ x
    
16.         merge(arr, left, mid, right);
    . a\" l\" n0 p$ W# i
17.     }0 |  L: a. G\" [' |
    
18. 3 M8 W  D- X6 Y- c5 {, v! A
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    0 A6 v+ V& w  Y) z5 o0 a
20.         int[] temp = new int[right - left + 1];4 E3 H# e$ m3 n! z3 s( ]% x/ W
    
21.         int i = left, j = mid + 1, k = 0;
      u) ?5 I$ a  ?. _1 S( v8 L# e
22. ! k\" T2 f4 h1 s3 k! h
    
23.         while (i <= mid && j <= right) {
    & O3 ~2 z0 W' v1 g% j
24.             if (arr[i] < arr[j]) {/ W- `\" Q1 }7 [% K
    
25.                 temp[k++] = arr[i++];% l8 ]1 }) T5 i  M7 H# c
    
26.             } else {
    3 B5 k4 H6 o- v5 {, g
27.                 temp[k++] = arr[j++];2 P: F# {' r/ ?
    
28.             }6 B8 y. Z$ {% d: i& ~# x0 D5 ~4 `
    
29.         }
    ) w7 x# ^' I9 y5 j, v% F! z
30. 
    4 t, I, S- ^5 y
31.         while (i <= mid) {
    + s% \- f/ G/ T3 ^3 F  w9 T
32.             temp[k++] = arr[i++];
    0 c. o# e  _% G\" R4 q% O# m0 w6 J$ B
33.         }: a! R  N2 f) u3 D
    
34. \" f* n1 t9 T0 O. m  Z) `# `$ Z% ]& ?3 t
    
35.         while (j <= right) {
    3 e8 ?1 c4 m# Y) v  J
36.             temp[k++] = arr[j++];0 \* {0 \. ^7 r' @0 i6 m
    
37.         }
    9 ^8 ]  M7 Z! Y& J1 L# Y
38. 7 ~( r$ u9 c3 k% \! ]& J' q& k7 x
    
39.         for (int m = 0; m < temp.length; m++) {% ?2 _0 ]! |5 P9 J4 T8 ]
    
40.             arr[left + m] = temp[m];& J( u7 Y3 A+ P! O
    
41.         }6 m6 t# l- Y, O* g  _
    
42.     }  `' f% w2 B6 }8 I  Q# H
    
43. }

复制代码

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

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

) i5 w! n- e" OmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   / N4 K1 ^$ i1 }
2.     if (left >= right) {3 g6 O; B  Z- ]2 O1 v8 H6 g' B' m0 D
   
3.         return;+ l) P  k7 w6 Q
   
4.     }; A. g\" E- \\" \5 k( m
   
5. 
   4 \7 }9 ^* V  x9 P/ m
6.     int mid = (left + right) / 2;
   , ?\" V! B1 k  r3 j
7.     mergeSort(arr, left, mid);% l  P4 j& O% ]' N8 q
   
8.     mergeSort(arr, mid + 1, right);1 L0 q. y( E; Q. k9 D, `3 \0 X
   
9.     merge(arr, left, mid, right);
   1 ]- I; {4 F* O6 y$ D
10. }
    ' P0 t( }4 D8 V+ e# \
11. 7 P  b& M\" W* Q
    

复制代码

这个函数使用递归的方式对数组进行排序。
, m  O: b4 e2 o' s- D
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {1 n, ^3 c/ _! b
   
2.     int[] temp = new int[right - left + 1];; r2 K, Z( u6 p% M- A
   
3.     int i = left, j = mid + 1, k = 0;8 o# ?: x2 a* m1 E4 Q! H& T) J# D
   
4. 
   # S) [: Q; B$ S5 E) W
5.     while (i <= mid && j <= right) {0 r. G6 M' H7 I' X, H4 v
   
6.         if (arr[i] < arr[j]) {
   & G\" Q3 P8 w; t
7.             temp[k++] = arr[i++];
   / ]% u' y% V# i8 C& ~\" l
8.         } else {5 R% p\" J: i, n6 |
   
9.             temp[k++] = arr[j++];
   ! H1 r) n\" E+ ]; E' ?  G
10.         }; e\" l# r7 C4 d9 ]
    
11.     }8 [, E' Q! z0 q9 {6 V7 F
    
12. ! e1 |0 T% C: z) {
    
13.     while (i <= mid) {7 t5 B5 q8 X0 k0 N, \& c
    
14.         temp[k++] = arr[i++];
    3 f$ @0 N7 x- D$ `
15.     }) m  y- Y& {- n7 j: N
    
16. 
    7 X! N5 g; w) f' n
17.     while (j <= right) {
    & i. t  c& q\" e* u: J. t: x
18.         temp[k++] = arr[j++];
    ) X' [1 f3 s# T9 L) B8 j% M
19.     }( c) s6 Z6 ~+ [7 U7 k- j) A: y1 a
    
20. ' Z; e: d; C' e3 D( e' M/ X  @: o
    
21.     for (int m = 0; m < temp.length; m++) {
    6 O3 E+ N0 D. w+ }2 v/ [
22.         arr[left + m] = temp[m];8 o- x, f1 ^4 {& Q; q
    
23.     }
    4 m9 `* n0 Q$ @  }) q
24. }
    % H; S( z1 q* G6 }# w6 L3 P7 d

复制代码

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

  Y2 I, @1 o6 Q/ B& d$ e7 Y4 Y合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

+ c6 y+ ]: r9 O4 N9 P最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

2 s0 }6 j& _( P" W需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

/ K& S: i3 K4 J; v这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
& \  Z7 W8 ?6 W5 M# B

. D# j9 p2 Z# n, C" a" l5 ~



' @/ _( E& s% O9 u" [" C2 i
8 Y/ T5 \+ _" J/ i