정렬 구현 문제

Solution

뭐 별거 없고 그냥 정렬을 구현하면 된다.
nlogn 정렬들 중 아무거나 구현하면 되는데 제일 간단하면서 안정적인 merge sort를 구현하였다.
퀵 소트, 힙 소트 등 기억이 잘 안나네 ㅋㅋ

Source Code

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        
        def mergesort(ls):
            if len(ls) == 1:
                return ls
            
            left = mergesort(ls[0:len(ls) // 2])
            right = mergesort(ls[len(ls) // 2:len(ls)])

            # merge
            new = []
            lidx, ridx = 0, 0
            while lidx + ridx < len(ls):
                if lidx < len(left) and (ridx == len(right) or left[lidx] < right[ridx]):
                    new.append(left[lidx])
                    lidx += 1
                else:
                    new.append(right[ridx])
                    ridx += 1
            
            return new
        
        return mergesort(nums)

912. Sort an Array

Problem link

Problem Summary

Solution

Source Code