일반 퀵정렬은 왼쪽 값에 있는 경우에 대해서 우측에 있는걸 다 비교하니까

1 2 3 4 5 6 7 8이면

왼쪽 1 기준, lt: 2 rt:5

2345 678 떼서 비교하고,

1 고정하고, 이렇게 해서 O(N^2)인건데

향상 된 퀵정렬(중앙값을 기준으로 고정값 정하면)

이 경우에는 정렬되어도, 5고정되고

1234,678 구분되면서

이것 끼리만 O(N)번 시도하고, 너비는 O(logN)일 껀데

왜 최악은 O(N^2)이라고 하는거임