재귀를 기반으로 하는 일반적인 알고리즘 문제를 잘게 나눠 반복적으로 해결하는 방법이다.
Merge Sort in Kotlin | Data Structures
<aside> 💡
병합정렬을 정렬해야 할 아이템들이 많다면 n log n의 좋은 성능을 보여준다 하지만 그 수가 적을때는 최선의 시간을 보장하지 못한다.
</aside>
![[출처] https://chercher.tech/kotlin/merge-sort-kotlin](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/09e168e7-ce51-4303-8846-b4007559bcc4/merge-sort-kotlin.png)
[출처] 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))
}