/ 알고리즘

Merge Sort

알고리즘 sort algorithm 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;
}