• 퀵 정렬와 같이 분할 정복 알고리즘임.
• 모든 숫자를 다 나눈 다음 병합하는 방식으로 정렬을 진행함.
• 퀵 정렬과 다른점은
  • 퀵 정렬 : 피벗을 통해 정렬 후 영역을 나눔.
  • 병합 정렬 : 먼저 영역을 나눌 수 있을 만큼 나눈 후 정렬.

알고리즘

• 정렬되지 않은 배열을 각각 하나의 원소만 포함하는 n개의 부분 배열로 분할.
• 부분 배열이 하나만 남을 때까지 반복하여 병합함. → 정렬된 배열이 생성됨.
• 즉, 배열을 계속 잘라서 나누고 병합함.

예시

정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정. → [4, 2, 6, 3, 7, 8, 5, 1]

1. 배열을 둘 로 나눔.
   1. 중간 인덱스 찾기
2. 나눈 배열들의 원소가 2개 이하가 될 때 까지 나눔.
3. 나눈 배열들을 정렬 후 나머지 배열들과 병합함.

분할
1. [4, 2, 6, 3, 7, 8, 5, 1]
2. [4, 2, 6, 3] [7, 8, 5, 1]
3. [4, 2] [6, 3] [7, 8] [5, 1]

정복
1. [2, 4] [3, 6] [7, 8] [1, 5]
2. [2, 3, 4, 6] [1, 5, 7, 8]
3. [1, 2, 3, 4, 5, 6, 7, 8]

소스코드 - Kotlin

fun main() {
    val intArray = intArrayOf(4, 2, 6, 3, 7, 8, 5, 1)
    println(mergeSort(intArray, 0, intArray.lastIndex))
}

fun mergeSort(array: IntArray, left: Int, right: Int) {
    if (left < right) {
        val mid = (left + right) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid + 1, right)
        merge(array, left, mid, right)
    }
}

fun merge(array: IntArray, left: Int, mid: Int, right: Int) {
    val L = array.copyOfRange(left, mid + 1)
    val R = array.copyOfRange(mid + 1, right + 1)

    var i = 0
    var j = 0
    var k = left
    val ll = L.size
    val rl = R.size
    while (i < ll && j < rl) {
        if (L[i] <= R[j]) {
            array[k] = L[i++]
        } else {
            array[k] = R[j++]
        }
        k++
    }

    while (i < ll) {
        array[k++] = L[i++]
    }
    while (j < rl) {
        array[k++] = R[j++]
    }
}

범위 및 함수 사용시 유의사항

• indices : IntRange타입을 반환하며**,** 수신객체의 전체 범위 반환. 위 예제 에선 0..6
• until : 범위의 마지막 요소를 포함하지 않음.
  • 0..5 => 0, 1, 2, 3, 4, 5
  • 0 until 5 => 0, 1, 2, 3, 4
• numbers.size , numbers.lastIndex 을 주의해서 사용.

장점