두 정렬된 묶음 합치기
1, 8과 3, 6처럼 각 묶음이 이미 정렬되어 있으면 앞의 값들을 비교해 작은 쪽부터 결과에 넣을 수 있다. 값 하나를 꺼낸 묶음에서는 다음 값을 비교한다. 두 묶음을 붙이기만 하는 것과 정렬 순서를 유지하며 병합하는 것은 다르다.
작은 문제에서 전체로
재귀적인 방식은 자료를 나누고 작은 부분을 정렬한 결과를 합친다. 반대로 작은 묶음부터 차례로 합치는 반복적인 구현도 가능하다. 같은 병합 정렬이라도 호출 구조가 반드시 하나로 정해져 있지는 않다.
시간과 공간의 비용
전형적인 구현은 단계마다 전체 원소 수에 비례하는 병합을 수행하며 단계 수는 로그 규모로 늘어난다. 배열에서 결과를 담는 보조 공간도 고려해야 한다. 연결된 구조를 쓰거나 제자리 병합을 구현하는 변형의 공간 특성을 기본 배열 구현과 혼동해서는 안 된다.
같은 키가 나올 때
병합 중 같은 키를 만났을 때 앞쪽 묶음의 원소를 먼저 선택하도록 하면 원래 순서를 유지할 수 있다. 이런 선택 규칙은 안정 정렬 구현에 중요하다. 안정성은 결과의 숫자 순서만으로 확인되지 않고 같은 키를 가진 항목들의 상대 순서를 살펴야 한다.