Daily LeetCode Challenge - 912. Sort an Array

Problem From.

https://leetcode.com/problems/sort-an-array/

오늘 문제는 여러가지 정렬 알고리즘 중에 하나를 선택해서 푸는 문제였다.

문제의 제한사항에 O(nlog(n)) 의 시간복잡도를 가지는 정렬 알고리즘을 사용하여 풀으라고 되어있으므로, merge sort (합병 정렬) 을 사용하여 문제를 풀었다.

합병 정렬은 분할과 정복을 활용하여 정렬을 하는 알고리즘으로, 배열을 작은 조각들로 나눈다음 정렬을 하고 다시 합치면서 정렬을 하게된다.

class Solution {
  
    fun sortArray(nums: IntArray): IntArray {
      val work = IntArray(nums.size)
      dfs(0, nums.size - 1, nums, work)
      return nums
    }
  
    private fun dfs(from: Int, to: Int, nums: IntArray, work: IntArray) {
        if (from == to) return
        val mid = (from + to) / 2
        dfs(from, mid, nums, work)
        dfs(mid + 1, to, nums, work)

        var i = from
        var j = mid + 1
        nums.copyInto(work, from, from, to + 1)
        var idx = from
        while (i <= mid && j <= to)
          nums[idx++] = if (work[i] <= work[j]) work[i++] else work[j++]
        while (i <= mid)
          nums[idx++] = work[i++]
        while (j <= to)
          nums[idx++] = work[j++]
    }
  
}