안정 정렬 vs 불안정 정렬 — 왜 Merge Sort가 필요한 순간이 있는가

원본: [(Alice, 90), (Bob, 80), (Carol, 90)]
키: 점수

안정 정렬 결과:   [(Bob, 80), (Alice, 90), (Carol, 90)]  ← Alice가 Carol보다 먼저
불안정 정렬 결과: [(Bob, 80), (Carol, 90), (Alice, 90)]  ← 순서 바뀜 가능

// 학생을 이름순으로 먼저 정렬하고, 그다음 성적순으로 정렬
// 안정 정렬이면 같은 성적 내에서 이름순이 유지됨
students.sort(Comparator.comparing(Student::getName));   // 1차: 이름
students.sort(Comparator.comparing(Student::getScore));  // 2차: 성적 (안정 정렬)

// 사실 Java에서는 Comparator 체이닝이 더 깔끔합니다
students.sort(Comparator.comparing(Student::getScore)
                        .thenComparing(Student::getName));

-- 두 번째 기준이 없으면 같은 score의 순서는 보장되지 않음
SELECT * FROM students ORDER BY score;

-- 안정적인 결과를 원하면 명시적으로
SELECT * FROM students ORDER BY score, name;

int[] arr = {3, 1, 4, 1, 5, 9};
Arrays.sort(arr); // Dual-Pivot Quick Sort (불안정)

Integer[] arr = {3, 1, 4, 1, 5, 9};
Arrays.sort(arr); // TimSort (안정)

List<String> list = Arrays.asList("banana", "apple", "cherry");
Collections.sort(list); // TimSort (안정)

원본: [1, 3, 5, 2, 4, 8, 7, 6]

Run 탐지:
  Run 1: [1, 3, 5]      (이미 오름차순)
  Run 2: [2, 4, 8]      (이미 오름차순)
  Run 3: [6, 7]         (내림차순 → 뒤집어서 오름차순)

병합:
  [1, 3, 5] + [2, 4, 8] → [1, 2, 3, 4, 5, 8]
  [1, 2, 3, 4, 5, 8] + [6, 7] → [1, 2, 3, 4, 5, 6, 7, 8]

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {   // <= 가 안정성의 핵심!
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, 0, arr, left, temp.length);
}

// 피벗 기준으로 교환하는 과정에서 순서가 바뀜
// 예: [3a, 2, 3b, 1] 피벗=3a
// 파티셔닝 후: [1, 2, 3a, 3b] 또는 [1, 2, 3b, 3a] → 보장 없음

// 원래 인덱스와 함께 정렬
int[][] indexed = new int[n][2];
for (int i = 0; i < n; i++) {
    indexed[i] = new int[]{arr[i], i};
}

Arrays.sort(indexed, (a, b) -> {
    if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
    return Integer.compare(a[1], b[1]); // 같은 값이면 원래 인덱스 순
});

// 안정 정렬로 일관된 결과 보장
@GetMapping("/users")
public List<User> getUsers(@RequestParam String sortBy) {
    List<User> users = userRepository.findAll();
    // Java의 List.sort()는 TimSort → 안정 정렬
    users.sort(Comparator.comparing(u -> getFieldValue(u, sortBy)));
    return users;
}

// 나쁜 예: 뺄셈은 오버플로우 위험
(a, b) -> a.getValue() - b.getValue()

// 좋은 예: Integer.compare 사용
(a, b) -> Integer.compare(a.getValue(), b.getValue())

// 더 좋은 예: Comparator.comparing 사용
Comparator.comparing(Entry::getValue)