소팅 알고리즘 중 시간복잡도가 O(nlogn)인 알고리즘들을 정리하려고 한다!
정확도는 leetcode - Sort an Array 제출을 통해 확인했다. (코드들은 모두 오름차순 정렬 코드이다)

Merge Sort

합병정렬. Divide & Conquer 방식으로 설계된 알고리즘으로, 입력으로 하나의 배열을 받고 연산 중 두 개의 배열으로 계속 쪼개어 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬된 배열을 출력

• Divide: 배열의 시작 위치와 종료 위치를 받아 합을 2로 나누어 그 위치를 기준으로 나눔 O(logn)
• Merge: 이미 정렬된 두 배열을 앞에서부터 비교해 맞는 값을 삽입 O(n)
  👉 Merge 시 별도의 공간을 둬 거기에 정렬. 따라서, O(2n)의 공간복잡도를 가짐

    void mergeSort(int[] nums, int s, int e) {
        if (s < e) {
            int mid = (s + e) / 2;
            
            mergeSort(nums, s, mid);
            mergeSort(nums, mid + 1, e);
            merge(nums, s, e, mid);
        }
    }
    
    void merge(int[] nums, int s, int e, int mid) {
        int i = s, j = mid + 1;
        
        int[] sortedNums = new int[e - s + 1];
        int index = 0;
        while ((i <= mid) && (j <= e)) {
            if (nums[i] > nums[j]) sortedNums[index++] = nums[j++];
            else sortedNums[index++] = nums[i++];
        }
        
        while (i <= mid) sortedNums[index++] = nums[i++];
        while (j <= e) sortedNums[index++] = nums[j++];
        
        for (i = s; i <= e; i++) {
            nums[i] = sortedNums[i - s];
        }
        
        printNums(nums);
    }

• is Stable: Yes
• is in-place: No

[8,5,6,2,4] 정렬 시
1. [5,8,6,2,4]
2. [5,6,8,2,4]
3. [5,6,8,2,4]
4. [2,4,5,6,8]

Quick Sort(사실 O(n²))

퀵정렬. Divide & Conquer 방식으로 설계된 알고리즘으로, 리스트 중 원소하나(피벗)를 골라 피벗을 기준으로 왼쪽 요소들은 피벗보다 작고, 오른쪽 요소들은 큰 수로 배치해 피벗을 기준으로 리스트를 둘로 나눔. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복하는 정렬 알고리즘

    void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
        
            quickSort(nums, left, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, right);
        }
    }
    
    int partition(int[] nums, int left, int right){
        int mid = (left + right) / 2;

        int pivot = nums[left];
        int i = left, j = right;

        while(i<j){
            while(pivot < nums[j]) j--;
            while(i < j && pivot >= nums[i]) i++;
            swap(nums, i, j);
        }

        nums[left] = nums[i];
        nums[i] = pivot;
        return i;
    }

• is Stable: No
• is in-place: Yes

[8,5,6,2,4] 정렬 시
1. [2,5,4,6,8]
2. [4,2,5,6,8]
3. [2,4,5,6,8]

최악의 경우에 O(n²)의 시간복잡도를 가짐 (평균적으로는 Θ(nlogn))
👉 근데 왜 "quick" 정렬일까?
1. 인접한 요소가 아닌 먼 거리에 있는 요소를 교환
2. 캐시 효율(한 번 선택된 피벗은 제외됨)

Heap Sort

힙정렬. 최대힙 트리나 최소힙 트리를 구성해 정렬하는 방법

• 오름차순 👉 최소힙 구성
• 내림차순 👉 최대힙 구성

방법

1. 최소힙 구성 (O(logn))
2. 최소 값을 꺼냄

위 과정을 모두 꺼낼 때 까지 반복, 매번 남은 수에 대해 힙을 재구성함
👉 가장 큰 몇 개의 수만 구할 때 더욱 유용

• is Stable: No
• is in-place: Yes (트리 뒤에 붙이는 방법으로 구현 시 따로 공간이 필요없음)