1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//! [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)

use super::{Algorithm, Array};

/// [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
pub struct MergeSort;

impl Algorithm for MergeSort {
  fn sort(&self, array: Array) {
    merge_sort(&array, 0, array.len() - 1);
  }

  fn name(&self) -> String {
    "Merge sort".to_string()
  }
}

fn merge_sort(array: &Array, left: usize, right: usize) {
  if left < right {
    let middle = (left + right) / 2;
    array.set_color(middle, [1.0, 0.0, 0.0, 1.0]);

    for i in left..middle {
      array.set_color(i, [0.0, 1.0, 0.0, 0.3]);
    }
    merge_sort(array, left, middle);

    for i in middle + 1..=right {
      array.set_color(i, [0.0, 0.0, 1.0, 0.3]);
    }
    merge_sort(array, middle + 1, right);

    merge(array, left, middle, right);

    for i in left..=right {
      array.reset_color(i);
    }
  }
}

fn merge(array: &Array, left: usize, middle: usize, right: usize) {
  let left_size = middle - left + 1;
  let right_size = right - middle;

  let left_array = sub_array(array, left, left_size);
  let right_array = sub_array(array, middle + 1, right_size);

  let mut i = 0;
  let mut j = 0;
  let mut k = left;
  let mut prev_k = k;

  while i < left_size && j < right_size {
    array.reset_color(prev_k);
    array.set_color(k, [1.0, 0.0, 0.0, 1.0]);
    prev_k = k;

    if left_array[i] <= right_array[j] {
      array.set(k, left_array[i]);
      i += 1;
    } else {
      array.set(k, right_array[j]);
      j += 1;
    }
    k += 1;
    array.wait(20);
  }

  array.reset_color(prev_k);

  while i < left_size {
    array.set(k, left_array[i]);
    i += 1;
    k += 1;
    array.wait(20);
  }

  while j < right_size {
    array.set(k, right_array[j]);
    j += 1;
    k += 1;
    array.wait(20);
  }
}

fn sub_array(array: &Array, begin: usize, size: usize) -> Vec<u32> {
  (0..size)
    .map(|i| {
      array.wait(10);
      array.get(begin + i)
    })
    .collect()
}