Strategy

• Break down into smaller problems
• Solve the smaller problems
• Combine results
• Recursive Sorting via divide-and-conquer

---

Merge Sort

Logics

Divide

• Partition S with n elements into two sub-sequences S1, S2 of about n/2 elements each.

Recursion

• Recursively sort S1 and S2.
• Performed implicitly by calling itself.

Conquer

• Merge S1, S2 into a unique sorted sequence.
• Merging time complexity : O(n)
• It can be implemented with DLL efficiently.

Codes

public void mergeSort(int[] values) {
        if (values == null || values.length <= 1)
            return;

        int middle = values.length / 2;
        int[] left = new int[middle];
        int[] right = new int[values.length - middle];

        for (int i = 0; i < middle; i++) {
            left[i] = values[i];
        }
        for (int i = 0; i < values.length - middle; i++) {
            right[i] = values[middle + i];
        }

        mergeSort(left);
        mergeSort(right);

        int l = 0;
        int r = 0;
        for (int i = 0; i < values.length; i++) {
            if (r >= right.length || (l < left.length && left[l] < right[r]))
                values[i] = left[l++];
            else
                values[i] = right[r++];
        }
    }

Analysis

• MergeSort의 경우 저장 공간이 2곳 필요.
• Height of merge sort tree is O(logn).
• The amount of work done at the nodes of depth is O(n).
• Best case : O(nlogn)
• Worst case : O(nlogn)
• Stable : Y
• In-place : N

---

Quick Sort

Logics

• Pick an element called pivot from the list.
• Partitioning : Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it, equal values can go either way.

Divide

• Pick pivot and partition S into L, E, G

Recurrence

• Sort L and G

Conquer

• Join L, E and G

Codes

import java.util.*;

public class QuickSortFunctional {

    public static int[] quickSort(int[] arr) {
        if (arr.length <= 1) return arr;

        int pivot = arr[arr.length - 1];

        List<Integer> less = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();

        for (int x : arr) {
            if (x < pivot) less.add(x);
            else if (x > pivot) greater.add(x);
            else equal.add(x);
        }

        // 재귀적으로 정렬
        int[] leftSorted = quickSort(listToArray(less));
        int[] rightSorted = quickSort(listToArray(greater));

        // 결과 병합 (less + equal + greater)
        return concat(leftSorted, listToArray(equal), rightSorted);
    }

    // Helper: List → int[]
    private static int[] listToArray(List<Integer> list) {
        int[] a = new int[list.size()];
        for (int i = 0; i < a.length; i++) a[i] = list.get(i);
        return a;
    }

    // Helper: 여러 배열을 하나로 합침
    private static int[] concat(int[]... arrays) {
        int total = 0;
        for (int[] arr : arrays) total += arr.length;

        int[] result = new int[total];
        int idx = 0;

        for (int[] arr : arrays) {
            for (int x : arr) result[idx++] = x;
        }

        return result;
    }
}

Analysis

• Partitioning sequence S with pivot x takes O(n) time.
• It can be implemented to run in-place.
• Depends on pivot.
• Worst case : O(n^2)
• Average case : O(nlogn)
• Randomized algorithm : O(nlogn)

---

In-place Quick Sort

Codes

public void inpQuickSort(int[] values, int left, int right) {
        if (left >= right) return;
        
        int pivotIndex = partition(values, left, right);
        
        inpQuickSort(values, left, pivotIndex - 1);
        inpQuickSort(values, pivotIndex + 1, right);
    }
    
    public int partition(int[] values, int leftBount, int rightBound) {
        int pivot = values[rightBound];
        int left = leftBount - 1;
        int right = rightBound;
        
        while(true) {
            while(values[++left] < pivot) { ; }
            while(right > leftBount && values[--right] > pivot) { ; }
            if (left >= right) break;
            else
                swap(values, left, right);
        }
        swap(values, left, rightBound);
        
        return left;
    }