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

2744557306

1 基础介绍
  \6 C  U. z, {" N2 c7 v7 {" X排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

以下是一些常见的排序算法：

冒泡排序（Bubble Sort）

- W: j0 S% ?0 Z+ S! q插入排序（Insertion Sort）

选择排序（Selection Sort）

( B% d+ F# ^# B# Y! u' L归并排序（Merge Sort）
0 i0 t6 e4 H! n, x  P+ {
快速排序（Quick Sort）

" [9 v: A/ f8 @6 h7 ?! i! n( A5 x( R& |堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
( C7 T* M$ w# c$ n
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

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

4 E. K* w9 j& t* y( _合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
/ d7 _9 ]" z: X) w# Z
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
: V: j' t& p1 N1 j% z0 W
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
& Q( H5 }4 Y# a& q
重复步骤 2，直到其中一个数组的元素全部放入 C 中。
6 e. Z8 ?: g8 k7 D6 n4 Y
将另一个数组中剩余的元素放入 C 中。

$ G5 `& j( {& g, V' E( ]  j归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
0 E9 L# J; U0 ^& k
0 o2 P7 d# R+ \原理简单示例
" `4 P0 ?, C7 P. H以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

- l8 m! M* @  F+ R! Q% y, A对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。

% ]( ~  b- n; Z因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
; l8 T0 \. k; V+ j7 K! x归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
) _$ R: s0 Q: S* p. `1 d8 p7 A* ?) D
这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
3 `5 H" t' Z% d) W7 T9 C
3 l, k0 x+ P; `' Q每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
& B" q4 N( @5 [6 y
6 w0 f3 Z# [# P% x归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
9 Y  P. f3 ^7 l
对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
/ ~# c8 w2 M3 q6 N% ^
, O- k: t, H" u" r) p1 Z8 \对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
( m/ `2 s) Q/ I% r- y1 {
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

/ v& ~, h0 r& }4 J对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
8 @( Y1 l( c' t2 x' z$ \  y
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

+ l) i' b+ u8 }% c+ i二、代码实现
2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   5 Q2 o' X) b8 I* O* c- G
2.     if len(arr) <= 1:. P7 n5 L3 n  t, d  Z, o
   
3.         return arr
   8 n) s( b' J) B; ~9 x4 r
4. 
   & J7 Q  u2 o8 l, Z
5.     # 将数组分成两个部分8 b- o7 |9 R: i
   
6.     mid = len(arr) // 2
   , l: L7 ]6 ^: S\" H& I3 M
7.     left_half = arr[:mid]
   6 q* k! h2 Q- G) H, Q  o1 c/ u
8.     right_half = arr[mid:]
   6 a; s6 H+ ~, l6 F. B; o3 B& @\" E
9. 
   4 c/ C4 p) O& n. u& b
10.     # 对左右两部分分别递归调用归并排序% t7 S8 P/ o: d( Y
    
11.     left_half = merge_sort(left_half)
    . U) G# W: T) S7 k
12.     right_half = merge_sort(right_half)
    5 T9 r8 K- g6 L5 d/ a8 n
13. 
    3 ~3 O0 z3 _  ~/ r/ ^
14.     # 合并左右两部分: Q) Q6 f\" \  t0 E
    
15.     return merge(left_half, right_half)7 k- G. f& ^- a
    
16. 
    % ]  m/ B# W0 n# _
17. def merge(left_half, right_half):
    ) q( Y( Q3 t! h! P0 r
18.     i = j = 0* Q7 M# R! }\" k1 n# y/ j2 ]0 M\" R
    
19.     merged = []
    * d$ ]. O8 o& K/ x; B% M& \# }. `
20. 
    , G) a1 J8 G- q/ |0 {3 M2 y0 K6 F
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中3 d1 {\" c$ T* D) V1 W+ o
    
22.     while i < len(left_half) and j < len(right_half):
    0 w. M1 n( d& x+ g1 u  y9 j; N
23.         if left_half[i] < right_half[j]:
    ! n( H) l6 g; z\" j- B- `5 ]\" `
24.             merged.append(left_half[i])
    - L* k\" p# b$ E! O4 z
25.             i += 1) K9 d( P* a4 o
    
26.         else:
    1 c+ l) |5 Q& J5 J+ H
27.             merged.append(right_half[j])6 c9 C) O) ^8 z! j- V
    
28.             j += 1
    0 E' {. S4 y2 X0 A5 a9 w
29. 8 y\" v' X1 s( n$ S
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    & v% p5 h6 X) N
31.     merged += left_half[i:]/ n8 a3 H: f5 [+ k8 M
    
32.     merged += right_half[j:]
    # Q1 T3 m5 j0 x% ]
33. 7 h. P\" D, T+ Q$ C
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):* |9 |. O. U( c5 O1 A6 ^9 S\" t
   
2.     if len(arr) <= 1:* L0 F$ u  c+ P  }5 _3 x; E* k
   
3.         return arr  g6 G* {; J, G) f. f2 f  ]
   
4. ! ]% k. u2 F$ B; B9 ~
   
5.     # 将数组分成两个部分0 d7 G\" h$ a' y1 R- _. R7 S
   
6.     mid = len(arr) // 2( n) S1 j+ ]/ q  v5 ?4 O4 Z& C
   
7.     left_half = arr[:mid]
   0 H& B5 ^) J1 N# c+ D
8.     right_half = arr[mid:]
   ! K( Y- B$ z4 }5 P\" S- d1 B
9. 
   ; C; R/ t: E, q3 [3 }' N5 M
10.     # 对左右两部分分别递归调用归并排序
    + e. J; `6 b- ]! |+ S
11.     left_half = merge_sort(left_half); {) z6 t$ ~' k* v\" V
    
12.     right_half = merge_sort(right_half)  J\" O\" d# b, ]0 x# u7 {' F
    
13.   N0 u* o5 i9 j8 d) e0 s. [
    
14.     # 合并左右两部分\" O7 Y. S1 i2 ^, h9 [, n
    
15.     return merge(left_half, right_half)+ _5 |  K6 I\" @: Z
    
16. ```
    9 _+ R' d6 O' z
17. ' ?2 _9 c\" R' @6 a  ], }
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    * A* [# ]/ G! I$ s# [# R

复制代码

merge() 函数

1. def merge(left_half, right_half):\" j+ \* m% I( r$ f  d* V
   
2.     i = j = 0
   ' f0 Q/ v- L5 t& H1 \$ n. o
3.     merged = []/ L\" b. r. l7 [! E3 W  n2 n
   
4. 
   ; z* M  W7 X. I' C: r7 `
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
     [1 K5 J/ d3 ]7 m\" E, {
6.     while i < len(left_half) and j < len(right_half):
   8 q+ t7 }8 O3 W2 ]2 U) I
7.         if left_half[i] < right_half[j]:
   5 C' S8 _( t! s0 O- D7 L6 c1 P
8.             merged.append(left_half[i])
   % [: p& r7 Z* W& t7 F\" C$ P
9.             i += 1/ n& R! i0 a1 s5 X5 l+ {
   
10.         else:! h* n7 p0 k2 I' Y
    
11.             merged.append(right_half[j])/ R7 u0 A( E- D7 F* A! A\" d3 a
    
12.             j += 1
    + J6 O8 O  W* B  H* f5 I
13. 4 M& x+ t# \( b+ V
    
14.     # 将左右两部分中剩余的元素添加到 merged 中- s! w5 V2 _, p/ p# ]) q
    
15.     merged += left_half[i:]$ m5 X' I: U( z- _7 y9 S
    
16.     merged += right_half[j:]# S4 F, h\" Q. P' p- e* M! D
    
17. 8 m6 _6 K9 p+ D4 ^. t9 R8 f
    
18.     return merged7 r8 f0 r% @0 t( m5 ?. C
    
19. ```
    8 X- n5 @2 i$ R4 k5 Y
20. 
    / S! k/ c5 V# O0 _: p. ]8 b
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
) m  K" ~6 x1 ]: H
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

+ \0 M8 r6 G) @& v9 i9 I将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
, [  F8 N6 Z0 Z; f& R
, T6 d, W  O) p3 d# E对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
& P  b4 k# Y. `% @3 x% D. M
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
0 ]/ S! v; b5 G( n6 N! Z
  U# ?* `2 M4 }/ w7 Y; L1 i8 b2 g0 @测试
, K5 H3 U! d0 A4 }0 r9 ^在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   - {# }\" `- E5 o# r( u2 s, v4 z5 u
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
( n( k+ N* K1 L  D1 r% ]
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
1 H& g" s/ D; P' \% l! A: e1 ~1 d2.2Java实现

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

1. public class MergeSort {) V6 e5 E' [* Z& X1 c, F
   
2.     public static void main(String[] args) {. E6 f\" H0 w\" ~/ N- j) u. i' Q
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   3 \$ r$ v; T: ^3 I- e- ~
4.         mergeSort(arr, 0, arr.length - 1);' U4 s  m& O% f0 h/ y# N( `
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]; {9 [, d$ {4 d
   
6.     }
   / P; x& i\" D/ y. p3 X5 y0 L. M
7. 
   / w' B) g0 a! R
8.     public static void mergeSort(int[] arr, int left, int right) {0 e- F  Y; k' h8 w' f, ]9 m! ]
   
9.         if (left >= right) {
   & n) Q) {' l, _4 I) g\" x0 J
10.             return;- C7 J7 ~2 ^; b! v- ^1 l
    
11.         }' ^1 G5 [4 V+ \! F( y7 r
    
12. 
    2 |, o1 G9 Q5 K: a* O: `- H
13.         int mid = (left + right) / 2;
    / e/ O( {+ T7 F9 [
14.         mergeSort(arr, left, mid);
    8 Y* `9 e3 q: k* r
15.         mergeSort(arr, mid + 1, right);$ S0 E3 D7 {# D6 Z9 o$ z
    
16.         merge(arr, left, mid, right);
    3 ^( N! d7 D\" w( P
17.     }
    5 m0 P# a8 \. Y4 e3 L  ~
18. $ b: J, v4 y- u: {\" P& n
    
19.     public static void merge(int[] arr, int left, int mid, int right) {& z# w! x2 Q% S& G+ ^. f
    
20.         int[] temp = new int[right - left + 1];: c% N+ A6 e, M/ L/ F
    
21.         int i = left, j = mid + 1, k = 0;
    ' E8 M# M$ y% k& h/ N/ [  n: H+ A- k
22.   C5 Q! z. C' i
    
23.         while (i <= mid && j <= right) {/ y# g8 H3 a6 z+ ?
    
24.             if (arr[i] < arr[j]) {6 \: U. Z; L# p, r% R
    
25.                 temp[k++] = arr[i++];
      c3 L& Z) [/ C5 C
26.             } else {6 y9 p+ [  l0 q2 G6 Z, f
    
27.                 temp[k++] = arr[j++];$ W* g- e1 D* q
    
28.             }
    3 S+ z- y* D7 C7 {7 w2 x
29.         }3 s2 \) Z- J* z1 z5 W
    
30. 
    3 H7 t+ f# q1 }
31.         while (i <= mid) {
    4 {- H0 V: S! x0 k\" l3 O
32.             temp[k++] = arr[i++];  ~\" o5 w- }4 j& ^
    
33.         }
    $ V& T0 w) O) Z- d: b7 T
34. 4 l0 ^1 _) ]5 }: v4 g2 Y
    
35.         while (j <= right) {7 W& p4 h6 U8 |% U* k7 V8 n- C
    
36.             temp[k++] = arr[j++];+ o' q# Z9 d- C5 \
    
37.         }
    7 K0 {6 e7 d- y6 E4 `+ e5 [2 `
38. 0 T9 D: j5 [. \. V  H7 |
    
39.         for (int m = 0; m < temp.length; m++) {
    $ V' x9 G4 r+ o
40.             arr[left + m] = temp[m];; {7 V: Q8 P+ z1 {
    
41.         }2 S$ O2 E( c3 \0 U# b/ t6 v
    
42.     }
    # Z1 i6 v. C+ R& R& O/ ]
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {- V) s. e+ b7 P+ y# o
   
2.     if (left >= right) {
   5 v0 D% A( |* ~) s/ r# N1 v) w- N# l
3.         return;
   . T' R, X8 ]& A; |: {) r4 k5 P' \0 |
4.     }/ D& }5 b8 D7 d1 I\" }1 P4 R
   
5. 
   0 k! @6 Y9 A4 |1 v8 O9 u\" X
6.     int mid = (left + right) / 2;
   8 L7 k, P+ q, P6 H
7.     mergeSort(arr, left, mid);
   - ~+ z  t. M\" C9 b
8.     mergeSort(arr, mid + 1, right);6 @4 c- {$ K% V- `' c+ n4 G( ]4 r
   
9.     merge(arr, left, mid, right);
   - P/ I8 Z$ ]9 ~6 A  [% v\" L7 x% X
10. }# ]5 c( M6 J' ]- h9 X- Z8 D9 `
    
11. \" g' u; C/ \, E$ C. `! l
    

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
2 g/ K: s+ ]4 s( h1 Y3 U) i# `
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   . Q' r8 n* o( g
2.     int[] temp = new int[right - left + 1];
   ( Y5 O9 f1 G\" e1 ?. j
3.     int i = left, j = mid + 1, k = 0;
     D2 b- ]# d( |$ C% K9 `
4. 
   # H# o- ^# x2 ]3 v+ P
5.     while (i <= mid && j <= right) {
   4 v! l9 N# q) d8 }- h2 {
6.         if (arr[i] < arr[j]) {( h6 l5 e5 Y, p% z3 d* o& n( f' [
   
7.             temp[k++] = arr[i++];  n- U+ D) k/ d1 K: v2 b) w
   
8.         } else {
   1 y3 s/ O. m2 n: l: J
9.             temp[k++] = arr[j++];  ~0 N8 i& |) \- @, W
   
10.         }7 a5 d% m: L; b1 S: H+ W! d
    
11.     }
    . M: ]4 D0 e\" \6 V* t+ D* d$ B
12. 
    8 W7 D% _' q, y% n+ d
13.     while (i <= mid) {
    1 p( k: B) [9 \6 w( B0 |' r
14.         temp[k++] = arr[i++];
    . |: j* `* ~\" A7 e. `
15.     }\" Q+ ~  L0 x' m3 h5 Q  M
    
16. 
    ! [0 Y$ u1 W- k0 L# Y) K
17.     while (j <= right) {
    * _0 A* n! p5 I; y3 N6 W* v
18.         temp[k++] = arr[j++];
    5 N$ m5 y$ W' D9 {/ K1 Z
19.     }
    + p( [% z! T5 H# r0 P
20. 1 {2 ~' }4 g( _; Q$ ~! O% E
    
21.     for (int m = 0; m < temp.length; m++) {
    8 _9 k! a+ I9 F( @! @\" O
22.         arr[left + m] = temp[m];( U; [* B, e' O. c) Y7 E; D
    
23.     }& d\" A- A3 C; p1 L; B9 x
    
24. }4 P; B( }7 |* i, x0 Z$ H( ^3 a
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
; u: O& a1 _0 I! [9 s
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
: {* s+ [2 \6 `* K8 w
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
  k* T% U- a; }, N: L
7 N& X5 l& ^0 u需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

6 C) |* v7 L/ X+ D( V( V& T* U这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
7 y+ j0 L) m7 O8 _& C
/ I0 E8 F8 U0 m" B! ?( O" u3 [

5 k3 ^9 P; c2 s4 f0 {
$ U8 e# b) b; K2 E' d