merge sort/heap sort

정의

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 개발자는 존 폰 노이만으로 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나간다. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다.
https://www.youtube.com/watch?v=XaqR3G_NVoo&ab_channel=AlgoRythmics

알고리즘

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

질문

1. merge sort, 퀵정렬, 삽입 정렬 중 이미 정렬이 되어있을 때 정렬 속도가 빠른 것 부터 나열하고 이유를 간단히 알려주실 수 있나요?
   : 가장 빠른것은 삽입 정렬입니다. 이미 정렬되어있기에 자료를 밀어내는 행위를 할 필요가 없기에 가장 빠릅니다. 그다음은 merge sort입니다.merge sort는 최악의 상황에서도 O(nlogn)의 시간 복잡도를 지니는것으로 알고있기에 2번째입니다. 마지막은 퀵정렬입니다. 이미 정렬된 경우 계속해서 피벗을 맨앞에 원소로 잡기에 최악의 시간복잡도를 가지게 되고 이때 O(n^2)의 시간복잡도를 지니게 됩니다.
2. merge sort의 동작 방식을 Divide & Conquer를 중심으로 설명해 주세요
   :Divide & Conquer 방식은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현합니다. 가장 작은 단위까지 Divide를 진행합니다 이후 합치면서 Conquer과정을 진행하는데 이때 두 배열의 각각의 원소들을 비교하여 정렬된 리스트를 만듭니다.
   1. merge sort가 메모리적 측면에서 어떠한 단점이 있는지 얘기해주세요
   : 장점이 데이터에 상태에 영향을 받지 않는다 인만큼 정렬하려고 하는 데이터의 크기만큼 메모리가 더 필요하다는 단점을 가지고 있습니다.
3. merge sort가 백엔드 단에서 어느 곳에 사용 될 수 있는지 설명해주세요 , 혹은 가능하다면, 사용되고 있는 실제 예시를 들어 설명해 주세요
   : 데이터 베이스에서 실제로 자주 사용된다고 알고있습니다. 두 테이블을 조인하면서 정렬할때 merge를 사용해서 정렬한다고 알고있습니다.
   1. Quick sort 와 Merge sort가 각각 어떤 Dataset에서 타 알고리즘보다 효율적인지 설명해주세요.
   : 퀵정렬의 경우 컴퓨터아키텍쳐에서 효율적인것으로 알고 있습니다. 메모리 참조를 지역화시켜 cpu캐시의 히트율을 올려줍니다. Merge sort의 경우 stable sort로 알고 있습니다 이에 DB상에서 데이터를 소팅할때 안정적이고 최선 최악 평균의 경우 O(nlogn)의 결과를 내기에 사용하는것으로 알고 있습니다.