합병 정렬(merge sort)

합병 정렬 알고리즘 개념

---

과정 설명

• 배열을 길이가 0 또는 1이 될 때까지 두 개의 배열로 나눈다.
• 각 나눠진 두개의 배열을 정렬하면서 합병
• 하나의 배열이 될 때까지 계속 합병

과정 상세 설명

정렬되지 않은 배열을 다른 배열에 정렬하면서 합병

 

4

3

7

1

5

6

2

3

4

1

7

5

6

2

두 개의 원소를 하나의 배열로 묶으면서 정렬한다. ex) (4,3)->(3,4)

 

 

3

4

1

7

5

6

2

1

3

4

7

2

5

6

두 개의 원소로 이루어진 배열 두 개를 하나의 배열로 묶으면서 정렬한다. ex) (3,4,1,7)->(1,3,4,7)

 

 

1

3

4

7

2

5

6

1

2

3

4

5

6

7

하나의 배열로 묶어서 정리

 

 

퀵 정렬 알고리즘 시간복잡도

---

Best: nlogn

Avg: nlogn

Worst: nlogn

 

개선방법

---

레코드를 연결리스트로 구성했을 경우, 링크 인덱스만 변경되어 데이터의 이동을 줄일 수 있다.(공부 필요)

 

References

---

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog