C++
#include<iostream>
#include<time.h>
#include "sort.h"
using namespace std;
const int N = 100000;
void MergeSort(int arr[], int l, int r, int divide)
{
int *first_Arr = new int[N + 1];
//int first_Arr[N + 1];
int first_Cnt = 0;
int *second_Arr = new int[N + 1];
//int second_Arr[N + 1];
int second_Cnt = 0;
for (int i = l; i <= divide; i++)
first_Arr[++first_Cnt] = arr[i];
for (int i = divide + 1; i <= r; i++)
second_Arr[++second_Cnt] = arr[i];
int first_index = 1;
int second_index = 1;
int present_Position = 0;
for (int i = l; i < l + (first_Cnt + second_Cnt); i++)
{
arr[i] = first_Arr[first_index] > second_Arr[second_index] ? second_Arr[second_index++] : first_Arr[first_index++];
if (first_index == first_Cnt + 1) // 첫번째 배열이 다 들어가서 두번째 배열만 넣어주면 되는 경우
{
for (int j = i + 1; j < l + (first_Cnt + second_Cnt); j++)
arr[j] = second_Arr[second_index++];
break;
}
else if (second_index == second_Cnt + 1) // 두번째 배열이 다 들어가서 첫번째 배열만 넣어주면 되는 경우
{
for (int j = i + 1; j < l + (first_Cnt + second_Cnt); j++)
arr[j] = first_Arr[first_index++];
break;
}
}
delete[] first_Arr;
delete[] second_Arr;
first_Arr = NULL;
second_Arr = NULL;
}
void NaturalMergeSort(int arr[], int l, int r)
{
int check_Cnt = 0; // 2개 일때 합병
int first_Merge_start = 1;
int check_Point;
int sw = 0;
for (int i = l + 1; i <= r; i++)
{
if (arr[i - 1] > arr[i])
{
check_Cnt++;
sw = 1;
if (check_Cnt == 1)
check_Point = i - 1;
}
if (check_Cnt == 2)
{
MergeSort(arr, first_Merge_start, i - 1, check_Point);
check_Cnt = 0;
first_Merge_start = i;
}
if (i == r && check_Cnt == 1)
MergeSort(arr, first_Merge_start, i, check_Point);
}
if (sw == 1)
NaturalMergeSort(arr, 1, N);
}
int main()
{
srand(time(NULL));
int *arr = new int[N + 1];
double start_time;
int rever = N;
for (int i = 1; i <= N; i++)
arr[i] = rever--;
start_time = clock();
NaturalMergeSort(arr, 1, N);
cout << "총 걸린 시간 = " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;
//for (int i = 1; i <= N; i++)
// cout << arr[i] << " ";
CheckSort(arr, N);
delete[] arr;
arr = NULL;
return 0;
}
ADL
Natural_Merge_Sort(arr[], l, r)
Arr_Cnt ← 1;
run[Arr_Cnt][0] ← 1;
for(i = l; i < r; i++) do {
if(arr[i] > arr[i+1]) then {
run[Arr_Cnt][1] = i;
Arr_Cnt ← Arr_Cnt + 1;
run[Arr_Cnt][0] = i + 1;
}
run[Arr_Cnt][1] = r;
while(Arr_Cnt > 1) do {
check ← 1;
for (i = 1; i <= Arr_Cnt – 1; i ← i + 2) do {
MergeSort(Arr,run[i][0], run[i+1][1], run[i][1]);
run[check][0] = run[i][0];
run[check][1] = run[i + 1][1];
check++;
}
run[check][0] = run[Arr_Cnt][0];
run[check][0] = run[Arr_Cnt][1];
Arr_Cnt ← Arr_Cnt - (check – 1 );
}
end Natural_Merge_Sort(arr[], l, r, divide)
MergeSort(arr[], l, r, divide)
for(i = divide + 1; i > l; i ← i – 1) do {
merge_Arr[i-1] = arr[i-1];
}
for(j = divide;j < r; j ← j + 1) do {
merge_Arr[r + divide – j] = arr[j + 1];
end MergeSort(arr[], l, r, divide)
volume.inf
