Merge sort algorithm

합병 정렬(merge sort)

합병 정렬은 분할정복 알고리즘이며 길이가 N인 리스트를 길이가 1인 리스트로 쪼개고 다시 쪼개진 각각의 리스트를 정렬하며 합병해 최종적으로 정렬된 리스트를 가지게 된다.

함수의 구조를 보면 알겠지만, 중앙 위치를 찾고 중앙 위치를 기준으로 좌측, 우측을 나눠 재귀 호출된다. 재귀 종료 조건은 start < end의 조건에 맞지 않는다면 더 나뉠 수 없다고 판단하여 쪼개는 과정이 종료된다. 최종적으로 마지막 merge함수를 이용해 각 리스트를 합병한다. 중요한 점은 이때 임시버퍼를 사용해야 하는데, 만약 임시버퍼를 사용할 수 없는 조건이라면 합병 정렬은 사용할 수 없다.

구현

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
fn main() -> Result<(), std::io::Error> {
let mut arr = [1, 30, 2, 1, 3, 4, 1, 9, 10, 13, 11];
let mut tmp: [isize; 11] = [0; 11];
tmp.clone_from_slice(&arr);
MySortor::sort(&mut arr, &mut tmp);
for v in &arr {
print!("{} ", v);
}
Ok(())
}

struct MySortor { }

impl MySortor {
pub fn sort(arr: &mut [isize], tmp: &mut [isize]) {
MySortor::merge_sort(arr, tmp, 0, arr.len() - 1);
}

fn merge_sort(arr: &mut [isize], tmp: &mut [isize], start: usize, end: usize) {
if start < end {
let mid = (start + end) / 2;
MySortor::merge_sort(arr, tmp, start, mid);
MySortor::merge_sort(arr, tmp, mid + 1, end);
MySortor::merge(arr, tmp, start, mid, end);
}
}

fn merge(arr: &mut [isize], tmp: &mut [isize], start: usize, mid: usize, end: usize) {
let mut p1 = start;
let mut p2 = mid + 1;
let mut store_index = start;
tmp.clone_from_slice(arr);

while p1 <= mid && p2 <= end {
if tmp[p1] <= tmp[p2] {
arr[store_index] = tmp[p1];
p1 += 1;
} else {
arr[store_index] = tmp[p2];
p2 += 1;
}
store_index += 1;
}
let e = mid as isize - p1 as isize;
for i in 0..=e {
arr[store_index + i as usize] = tmp[p1 + i as usize];
}
}
}

필기노트

merge-sort-1

레퍼런스

[알고리즘] 합병 정렬(merge sort)이란

[자료구조 알고리즘] 병합정렬(Merge Sort) 구현하기

Share