merge-insertion sort

Merge Sort와 Insertion Sort를 결합한 Merge Insertion Sort

작동방식

1. 우선 N개요소를 2/N의 크기만큼으로 나누어 줌
2. 나뉘어진 요소의 크기가 K보다 크다면 다시 절반으로 나누어 줌
   
3. K개보다 작은 크기로 나뉘어졌다면 각 요소들을 Insertion Sort로 정렬해줌
4. Insertion Sort로 정렬해준 K개의 요소들을 Merge Sort로 정렬하며 병합해줌
5. 모두 정렬이 될때 까지 반복
   

구현

void merge_insertion_sort_vec(std::vector<int> &vec, int left, int right, int size)
{
	if (left >= right)
		return;
	// 비교할 크기가 size보다 작다면 삽입정렬
	if (right - left + 1 <= size)
	{
		insertion_sort(vec, left, right);
		return;
	}
	// 크기를 절반으로 나눠 재귀로 호출
	int mid = (left + right) / 2;
	merge_insertion_sort_vec(vec, left, mid, size);
	merge_insertion_sort_vec(vec, mid + 1, right, size);
	// 여태 나눠진 모든 리스트들이 size보다 작아져서 삽입정렬이 완료됬다면 합병정렬로 합쳐주기
	merge_sort(vec, left, mid, right);
}

출처

https://iq.opengenus.org/merge-insertion-sort/amp/