1use super::Infite;
2use super::Sort;
3use core::fmt::Debug;
4
5#[derive(Debug)]
7pub struct MergeSort<T> {
8 arr: Vec<T>,
9}
10
11impl<T> MergeSort<T>
12where
13 T: Copy + Default + Infite + Debug,
14{
15 fn merge_sort_by<F>(&mut self, f: F)
16 where
17 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
18 {
19 let start = 0;
20 let end = self.arr.len() - 1;
21 inner_merge_sort(&mut self.arr, start, end, f);
22 }
23}
24
25impl<T> From<Vec<T>> for MergeSort<T> {
26 fn from(arr: Vec<T>) -> Self {
27 Self { arr }
28 }
29}
30
31impl<T: core::clone::Clone> From<&[T]> for MergeSort<T> {
32 fn from(arr: &[T]) -> Self {
33 Self { arr: arr.into() }
34 }
35}
36
37impl<T> Sort<T> for MergeSort<T>
38where
39 T: core::cmp::PartialOrd + Default + Copy + Infite + Debug,
40{
41 fn inner(&self) -> Vec<T> {
42 self.arr.clone()
43 }
44
45 fn sort_by<F>(&mut self, f: F)
46 where
47 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
48 {
49 self.merge_sort_by(f)
50 }
51}
52
53fn inner_merge_sort<T, F>(array: &mut Vec<T>, p: usize, r: usize, f: F)
54where
55 T: Default + Copy + Infite + Debug,
56 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
57{
58 if p < r {
59 let q = (p + r) / 2;
60 inner_merge_sort(array, p, q, f);
61 inner_merge_sort(array, q + 1, r, f);
62 inner_merge(array, p, q + 1, r + 1, f); }
64}
65
66fn inner_merge<T, F>(arr: &mut [T], p: usize, q: usize, r: usize, f: F)
67where
68 T: Default + Copy + Infite + Debug,
69 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
70{
71 log::info!("p = {}, q = {}, r = {}", p, q, r);
72 let n1 = q - p;
73 let n2 = r - q;
74
75 let max_value = T::max_value();
77 let mut l_arr = vec![max_value; n1 + 1];
78 let mut r_arr = vec![max_value; n2 + 1];
79
80 for i in 0..n1 {
81 if let Some(v) = arr.get(p + i) {
82 if let Some(t) = l_arr.get_mut(i) {
83 *t = *v;
84 }
85 }
86 }
87
88 log::info!("l_arr = {:?}", l_arr);
89
90 for j in 0..n2 {
91 if let Some(v) = arr.get(q + j) {
92 if let Some(t) = r_arr.get_mut(j) {
93 *t = *v;
94 }
95 }
96 }
97 log::info!("r_arr = {:?}", r_arr);
98
99 let mut i = 0usize;
100 let mut j = 0usize;
101
102 for k in p..r {
103 if f(&l_arr[i], &r_arr[j]) {
104 if let Some(v) = arr.get_mut(k) {
105 *v = l_arr[i];
106 }
107 i += 1;
108 } else {
109 if let Some(v) = arr.get_mut(k) {
110 *v = r_arr[j];
111 }
112 j += 1;
113 }
114 }
115}
116
117#[test]
118fn test_merge_sort() {
119 impl Infite for i32 {
120 fn max_value() -> Self {
121 i32::MAX
122 }
123 fn min_value() -> Self {
124 i32::MIN
125 }
126 }
127 let array = vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
128
129 let mut merge_sort = MergeSort::from(array);
130 println!("merge_sort: {merge_sort:?}");
131 merge_sort.sort();
132 assert!(merge_sort.is_sort());
133 println!("merge_sort: {merge_sort:?}");
134}
135
136type Link<T> = Option<Box<ListNode<T>>>;
137#[derive(Debug, PartialEq)]
139pub struct ListNode<T> {
140 pub val: T,
141 pub next: Link<T>,
142}
143
144#[allow(dead_code)]
145fn merge_two_lists_recu<T: Ord + Copy>(list1: Link<T>, list2: Link<T>) -> Link<T> {
146 match (list1, list2) {
147 (Some(l), None) => return Some(l),
148 (None, Some(r)) => return Some(r),
149 (None, None) => return None,
150 (Some(l), Some(r)) => {
151 if l.val <= r.val {
152 return Some(Box::new(ListNode {
153 next: merge_two_lists(l.next, Some(r)),
154 val: l.val,
155 }));
156 } else {
157 return Some(Box::new(ListNode {
158 next: merge_two_lists(Some(l), r.next),
159 val: r.val,
160 }));
161 }
162 }
163 }
164}
165
166#[allow(dead_code)]
167fn merge_two_lists_no_recu<T: Ord + Copy>(list1: Link<T>, list2: Link<T>) -> Link<T> {
168 let mut output = None;
169
170 let mut next_node_pos = &mut output;
171 let mut l1_opt = list1;
172 let mut l2_opt = list2;
173 loop {
174 let mut l1 = match l1_opt {
175 Some(l1) => l1,
176 None => {
177 *next_node_pos = l2_opt;
178 break;
179 }
180 };
181 let mut l2 = match l2_opt {
182 Some(l2) => l2,
183 None => {
184 *next_node_pos = Some(l1);
185 break;
186 }
187 };
188
189 if l1.val < l2.val {
190 l1_opt = l1.next.take();
191 l2_opt = Some(l2);
192 *next_node_pos = Some(l1);
193 } else {
194 l2_opt = l2.next.take();
195 l1_opt = Some(l1);
196 *next_node_pos = Some(l2);
197 }
198
199 next_node_pos = &mut next_node_pos.as_mut().unwrap().next;
200 }
201
202 output
203}
204
205pub fn merge_two_lists<T: Ord>(mut list1: Link<T>, mut list2: Link<T>) -> Link<T> {
207 let mut head = None;
208 let mut tail = &mut head;
209
210 loop {
211 match (list1, list2) {
212 (Some(mut l1), Some(mut l2)) => {
213 if l1.val < l2.val {
214 list1 = l1.next.take();
215 list2 = Some(l2);
216 tail = &mut tail.insert(l1).next;
217 } else {
218 list1 = Some(l1);
219 list2 = l2.next.take();
220 tail = &mut tail.insert(l2).next;
221 }
222 }
223 (l1, l2) => break *tail = l1.or(l2),
224 }
225 }
226
227 head
228}
229
230#[cfg(test)]
231mod tests {
232 use super::*;
233 macro_rules! list {
234 () => { None };
235 ($head:expr $(, $val:expr)* $(,)?) => {
236 Some(Box::new(ListNode {
237 val: $head,
238 next: list!($($val),*),
239 }))
240 };
241 }
242
243 #[test]
244 fn test_merge_list() {
245 let list1 = list!(1, 3);
246 println!("list1: {:#?}", list1);
247 let list2 = list!(2, 4);
248 println!("list2: {:#?}", list2);
249
250 let result = list!(1, 2, 3, 4);
251 assert_eq!(result, merge_two_lists(list1, list2));
252 }
253}