분할 정복 알고리즘을 사용하는 매우 빠른 정렬 방법

분할정복

• 어떤 한 문제를 조금식 나눠가면서 풀 수 있는 문제 단위로 나눈 다음 다시 합쳐 해결

출처 : https://namu.wiki/w/분할 정복 알고리즘

정렬 과정

1. 배열 안에 있는 한 요소를 선택한다. 이렇게 고른 요소를 피벗이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽, 큰 요소들은 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽, 오른쪽을 다시 정렬한다.
4. 더 이상 나눠질 수 없을 때 까지 1 ~ 3번을 반복한다.

출처 : https://akdl911215.tistory.com/386

시간복잡도

• 평균 : nlogN
• 최악 : n^2