이전 포스팅에서 살펴본 정렬 알고리즘들은 평균, 최악의 경우 $O(n^2)$의 시간복잡도를 가지게 되었다.  병합 정렬 (Merage Sort)"병합 정렬"(또는 합병 정렬)은 문제를 분할하고, 문제를 정복하여 합치는 분할정복을 기반으로 한 정렬 알고리즘이다.   정렬 과정이러한 분할정복은 "하향식"과 "상향식"구현으로 구분할 수 있는데,병합 정렬에선 하향식 구현방식을 대부분 사용한다. 하향식(TopDown)방식으로 구현한 병합 정렬의 과정은 다음과 같다. (아래 그림은 정확한 Top-Down 방식은 아니지만, 분할되고 정복되는 순서만 차이 있을 뿐, 방법은 동일하다.)리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 부분 리스트의 길이가 1이하가 될 때까지 재귀적으로 위의 과정을 반복한다. (길..

"정렬 알고리즘"은 일련의 원소들에 대해 정해진 규칙에 맞게 재배열하는 알고리즘이다. 정렬 알고리즘은 현대까지도 계속 발명 될 정도로, 많은 알고리즘이 존재하지만 이중 대표적으로 몇가지만 살펴볼것이다.   정렬 알고리즘 분류 기준정렬 알고리즘은 여러 기준으로 분류된다.  안정 정렬 vs. 불안정 정렬 "안정 정렬"이란, 정렬조건이 동일한 원소가 여러개 있을 때, 입력 때와 동일한 순서로 정렬되는 정렬 알고리즘이다.반면, "불안정 정렬" 입력 때와 동일한 순서로 졍렬되는 것을 보장하지 않는다.  "안정 정렬"은 정렬조건이 동일한 원소들의 순서를 보장해야할 때, 유용하게 사용될 수 있다. 예를 들어, 온라인 쇼핑몰에서 구매자의 구매 요청이 요청 순서대로 쌓인다고 가정해보자. 이때, 등급이 높은 회원부터 배송..