/ 알고리즘

# Merge Sort

https://4am.kr/merge-sort/
``````#include<iostream>
using namespace std;
//define data array size
#define MAX 8

int num[MAX] = {12, 59, 34, 23, 17, 61, 31, 14};

void merge(int low, int mid, int high)
{
int tmp[MAX]; //temp array only used in merge function
int i;  //meaning-less iterator only used in merge function
//index of 2 pieces each
//1st piece: low --- mid
//2nd piece: mid + 1 --- high
int p1 = low, p2 = mid + 1;
int pos = low; //index of result array
//compare two arrays and choose 1 piece
//and copy to result
//until over the range of each pieces
//1st piece: low --- mid
//2nd piece: mid + 1 --- high
while(p1 <= mid && p2 <= high)
{
if(num[p1] < num[p2]) tmp[pos++] = num[p1++];
else tmp[pos++] = num[p2++];
}
//if p1 is larger than mid,
//peace 1 = copied; piece 2 = not copied;
if(p1 > mid)
{
for(int i = p2; i <= high; i++)
tmp[pos++] = num[i];
}
//otherwise
//peace 2 = copied; piece 1 = not copied;
else
{
for(int i = p1; i <= mid; i++)
tmp[pos++] = num[i];
}
//copy results to original array
for(int i = low; i <= high; i++)
num[i] = tmp[i];
}

void merge_sort(int low, int high)
{
if(low < high)
{
int mid = (low + high)/2;
//divide data array into 2 pieces
merge_sort(low, mid);
merge_sort(mid + 1, high);
//merge 2 pieces into 1
merge(low, mid, high);
}
}

void print()
{
for(int i = 0; i < MAX; i++)
cout << num[i] << endl;
cout << endl;
}

int main()
{
cout << "not sorted data" << endl;
print();
merge_sort(0, MAX - 1);
cout << "sorted data by merge sort" << endl;
print();
return 0;
}
``````

#### at4am

❤️ for me and dummies.