정렬 시간복잡도 구해보기

외부 루프 (i): n번 반복

내부 루프 (j): (n-i)번 반복

외부 루프 (i): n-1번 반복
    • 배열을 처음부터 끝까지 순회

내부 루프 (j): (n-i-1)번 반복
    • 첫 번째 반복: n-1번 비교
    • 두 번째 반복: n-2번 비교
    • 마지막 반복: 1번 비교

\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}

최선의 경우: O(n) - 배열이 이미 정렬되어 있는 경우

평균의 경우: O(n²)

최악의 경우: O(n²) - 배열이 역순으로 정렬되어 있는 경우

외부 루프는 n-1번 실행 (i는 1부터 n-1까지)

분할 과정: 배열을 반으로 나누는 과정이 log n번 발생

병합 과정: 각 레벨에서 n개의 원소를 병합하는 데 O(n)의 시간이 소요

최선의 경우: O(n log n) - 피벗이 항상 중간 값으로 선택되는 경우

평균의 경우: O(n log n) - 일반적인 상황에서의 성능

최악의 경우: O(n²) - 이미 정렬된 배열이나 피벗이 항상 최소/최대값인 경우