🚀 std::sort() vs mergeSort()

---

📌 1️⃣ std::sort()와 mergeSort()의 차이

✅ std::sort()는 Introsort 사용

• 퀵 정렬 (Quick Sort) + 힙 정렬 (Heap Sort) + 삽입 정렬 (Insertion Sort) 조합
• 평균적으로 O(N log N) 성능
• 최악의 경우에도 O(N log N) 보장
• 추가 메모리 사용 O(1) (제자리 정렬, In-Place Sort)

✅ mergeSort()는 항상 O(N log N)

• 항상 일정한 성능 유지 (O(N log N))
• 추가 메모리 사용 O(N) 필요 (배열 복사 과정 있음)
• 안정 정렬(Stable Sort) → 같은 값의 순서 유지 가능

---

📌 2️⃣ 시간 복잡도 비교

정렬 방법 평균 시간 복잡도 최악의 경우 추가 메모리 사용

🚀 std::sort() (Introsort)	O(N log N)	O(N log N)	O(1) (제자리 정렬)
🚀 mergeSort() (합병 정렬)	O(N log N)	O(N log N)	O(N) (배열 복사 필요)

---

📌 3️⃣ 실제 속도 테스트 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;
using namespace chrono;

// 두 개의 정렬된 배열을 병합하는 함수
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);

    for (int k = left; k <= right; k++) arr[k] = temp[k - left];
}

// 합병 정렬 (Merge Sort)
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    const int N = 1000000;  // 배열 크기
    vector<int> arr1(N), arr2(N);

    // 랜덤 데이터 생성
    for (int i = 0; i < N; i++) arr1[i] = arr2[i] = rand();

    // ✅ std::sort() 실행 시간 측정
    auto start = high_resolution_clock::now();
    sort(arr1.begin(), arr1.end());
    auto end = high_resolution_clock::now();
    cout << "std::sort() 실행 시간: " << duration<double>(end - start).count() << " 초\n";

    // ✅ mergeSort() 실행 시간 측정
    start = high_resolution_clock::now();
    mergeSort(arr2, 0, N - 1);
    end = high_resolution_clock::now();
    cout << "mergeSort() 실행 시간: " << duration<double>(end - start).count() << " 초\n";

    return 0;
}

---

📌 4️⃣ 실행 결과 예시

(컴퓨터 성능에 따라 다를 수 있음)

std::sort() 실행 시간: 0.27 초
mergeSort() 실행 시간: 0.85 초

✅ 결론:

• std::sort()가 일반적으로 mergeSort()보다 3배 이상 빠름 🚀
• mergeSort()는 추가 메모리(O(N)) 사용으로 인해 속도가 느려짐

---

📌 5️⃣ 언제 mergeSort()를 써야 할까?

상황 어떤 정렬을 선택?

🚀 메모리를 아끼고 싶다	std::sort() 사용! (제자리 정렬, O(1) 메모리)
🚀 안정적인 정렬이 필요하다 (Stable Sort)	mergeSort() 사용! (순서 유지 가능)
🚀 최악의 경우에도 O(N log N) 성능 보장	mergeSort() 사용!
🚀 빠른 정렬이 필요하다	std::sort() 사용! (일반적으로 더 빠름)

---

📌 6️⃣ 최종 결론

✅ 🚀 std::sort()가 더 빠르고 효율적이므로 기본적으로 std::sort()를 사용하자!
✅ 🚀 하지만, "안정 정렬(Stable Sort)"이 필요하다면 mergeSort()를 사용할 수 있다.