특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균 시간 복잡도O(N * logN), 최악 O(N^2) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 1. 버퍼의 요소 중 하나를 피벗(pivot)으로 지정 보통 맨 왼쪽, 중앙, 맨 오른쪽으로 지정하고, 본 포스팅은 피벗을 맨 왼쪽으로 함 2. 피벗보다 작은 값을 피벗의 왼쪽으로 이동, 피벗보다 큰 값을 피벗의 오른쪽으로 이동 3. 피벗을 기준으로 왼쪽 버퍼와 오른쪽 버퍼를 나누어 각 재귀 함수 호출 구현에서 중요한 점은 퀵 정렬은 추가 버퍼를 사용하지 않는 In-place sort라는 것이다. 따라서 2번 과정에서 새로운 버퍼를 이용하지 않고, 한 버퍼에서 s..

# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..