정렬과 관계가 있는 프로세스로 합병(merge)이 있다.
쌍방 합병(two-way-merging)이란 2개의 정렬된 배열을 하나의 정렬된 배열로 합하는 것을 의미한다.
합병 프로시저를 반복 적용하여 배열을 정렬할 수 있다.
예를 들면 16개 아이템을 가진 배열을 정렬하기 위해서, 각각 크기가 8인 2개의 부분배열로 분할하고,
그 두 부분배열을 각각 정렬하고, 그들을 합병하여 정렬된 배열을 만들 수 있다.
같은 방법으로 크기가 8인 부분배열을 각각 크기가 4인 2개의 부분배열로 분할하고, 부분배열들은 정렬하고 합병할 수 있다.
궁극적으로 부분배열의 크기는 1이 될 것이고, 크기가 1인 배열은 사소하게(trivially) 정렬된다.
이 절차를 “합병정렬(Merge-sort)"이라고 한다.
n개 아이템을 가진 배열이 주어지면(간편하게 하기 위해서 n은 2의 거듭제곱이라고 가정), 합병정렬은 다음과 같은 절차로 진행된다.
분할 : 배열은 n/2개 아이템을 가진 2개의 부분배열로 분할한다.
정복 : 정렬함으로써 각 부분배열을 정복한다(푼다). 배열이 충분히 작지 않으면 재귀 호출을 한다.
통합 : 부분배열에 대한 답들을 합병하여 하나의 정렬된 배열로 만든다.
합병 정렬의 기본 아이디어는 3단계로 요약된다.
정렬될 리스트 List = ( 6 ,2 ,8 ,1 ,3 ,9 ,4 ,5 ,10 ,7 ) 가 있다고 가정하자.