📌 병합 정렬 (Merge Sort)

• 분할 정복(Divide & Conquer)
  1. 리스트를 반으로 계속 분할
  2. 각 부분 리스트를 정렬
  3. 다시 합치면서 전체를 정렬

🧑‍💻 코드 (Python 구현)

def merge_sort(arr, reverse=False):
    # 원소가 하나면 그대로 반환
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid], reverse)
    right = merge_sort(arr[mid:], reverse)

    return merge(left, right, reverse)


def merge(left, right, reverse):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if reverse:
            if left[i] > right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1
        else:
            if left[i] < right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


# 실행 예시
import random
arr = random.sample(range(1, 101), 10)
print("원본:", arr)
print("오름차순:", merge_sort(arr))
print("내림차순:", merge_sort(arr, reverse=True))

원본: [42, 7, 55, 13, 87, 65, 29, 90, 33, 11]
오름차순: [7, 11, 13, 29, 33, 42, 55, 65, 87, 90]
내림차순: [90, 87, 65, 55, 42, 33, 29, 13, 11, 7]

📌 퀵 정렬

• 분할 정복 기반 정렬
  1. 기준값(pivot) 선택
  2. pivot보다 작은 값, 큰 값으로 분리
  3. 각 부분 배열을 재귀적으로 정렬 후 합침

🧑‍💻 코드 (Python 구현)

def quick_sort(arr, reverse=False):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]

    if reverse:
        return quick_sort(greater, reverse) + [pivot] + quick_sort(less, reverse)
    else:
        return quick_sort(less, reverse) + [pivot] + quick_sort(greater, reverse)


# 실행 예시
import random
arr = random.sample(range(1, 101), 10)
print("원본:", arr)
print("오름차순:", quick_sort(arr))
print("내림차순:", quick_sort(arr, reverse=True))

원본: [25, 90, 12, 76, 33, 48, 15, 62, 81, 7]
오름차순: [7, 12, 15, 25, 33, 48, 62, 76, 81, 90]
내림차순: [90, 81, 76, 62, 48, 33, 25, 15, 12, 7]

✨ 정리

• 병합 정렬(Merge Sort): 안정 정렬, $O(n log n)$, 항상 일정한 성능
• 퀵 정렬(Quick Sort): 평균 $O(n log n)$, 최악 $O(n^2)$ -> pivot 선택중요
• 두 알고리즘 모두 분할 정복(Divide & Conquer) 의 대표적인 예시