재귀를 기반으로 하는 일반적인 알고리즘 문제를 잘게 나눠 반복적으로 해결하는 방법이다.

Merge Sort in Kotlin | Data Structures

<aside> 💡

병합정렬을 정렬해야 할 아이템들이 많다면 n log n의 좋은 성능을 보여준다 하지만 그 수가 적을때는 최선의 시간을 보장하지 못한다.

</aside>

병합정렬의 과정


[출처] https://chercher.tech/kotlin/merge-sort-kotlin

[출처] https://chercher.tech/kotlin/merge-sort-kotlin

구현


양쪽 리스트 나누기

fun mergeSort(list: List<Int>): List<Int> {
    if (list.size == 1) {
        return list
    }

    val middleIdx = list.size / 2
    val leftList = list.subList(0, middleIdx)
    val rightList = list.subList(middleIdx, list.size)

    return merge(mergeSort(leftList), mergeSort(rightList))
}
  1. 중앙을 기준으로 왼쪽리스트 오른쪽 리스트를 나눠준다.
  2. 왼쪽 리스트와 오른쪽 리스트는 1개만 남을때까지 계속 나눈다
  3. 1개씩 남고 나서 하나하나 붙여가면서 정렬을 한다.
  4. 이를 끝까지 반복한다.