| Name | 최선 | 평균 | 최악 | 메모리 |

| :------: | :------: | :------: | :------: | :-----: |

| 버블정렬 | O(n) | O(n^2) | O(n^2) | O(1) |

| 선택정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |

| 삽입정렬 | O(n) | O(n^2) | O(n^2) | O(1) |

| 힙정렬 | O(n) | O(nlogn) | O(nlogn) | O(1) |

| 병합정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |

| 퀵정렬 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) |

- Divide and Conquer(분할-정복) 알고리즘에 속함

- 둘 다 점점 탐색할 배열의 크기를 쪼개서 재귀함수에 넘겨줌

- 병합 정렬과 달리 다른 메모리 공간을 사용하지 않음

- 병합정렬을 `stable` 하지만, 퀵 정렬을 `unstable`함. (원소들 중 같은 값이 있는 경우 초기 순서가 달라질 수 있기 때문)

1. Lomutos' Partition (배열의 맨 마지막 값을 pivot으로 정하는 방식)

2. Hoare's Parition (물리적으로 배열의 중간값을 pivot으로 정하는 방식)