Mergesort(합병정렬)

Basic Concept

---

A process related to sorting is merging. By two-way merging we mean combining two sorted arrays into one sorted array. By repeatedly applying the merging procedure, we sort an array. For example, to sort an array of 16 items, we can divide it into two subarrays, each of size 8, sort the two subarrays, and then merge them to produce the sorted array. In the same way, each subarray of size 8 can be divided into two subarrays of size 4, and these subarrays can be sorted and merged. Eventually, the size of the subarrays will become 1, and an array of size 1 is trivially sorted. This procedures is called Mergesort.

 

Example The steps done sorting with Mergesort

 

👉 합병이란 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 것을 의미한다. 합병 절차를 반복적용함으로써 배열을 정렬할 수 있으며, 이를 합병정렬이라고 한다.

 

 

Mergesort Algorithm

---

Algorithm Design

1. Divide the array into two subarrays each with n/2 items.
2. Conquer(solve) each subarray by sorting it. Unless the array is sufficiently small, use recursion to do this.
3. Combine the solutions to the subarrays by merging them into a single sorted array.

 

Pseudo Code

• Mergesort

void mergesort2(index low, index high)
{
  index mid;

  if (low < high) {
    mid = (low + high) / 2;
    mergesort2(low, mid);
    mergesort2(mid+1, high);
    merge2(low, mid, high);
  }
}

void merge2(index low, index mid, index high)
{
  index i, j, k;
  keytype U[low..high]; // A local array needed for the merging

  i = low; j = mid + 1; k = low;
  while (i <= mid && j <= high) {
    if (S[i] < S[j]) {
      U[k] = S[i];
      i++;
    }
    else {
      U[k] = S[j];
      j++;
    }
    k++;
  }
  if (i > mid)
    move S[j] through S[high] to U[k] through U[high];
  else
    move S[i] through S[mid] to U[k] through U[high];
  move U[low] through U[high] to S[low] through S[high];
}

 

Source Code

• sorting.h

// File: sorting.h
#ifndef SORTING_H
#define SORTING_H

namespace algorithms
{
  void mergesort2(int data[ ], int low, int high);
  // Problem: Sort n keys in nondecreasing sequence.
  // Inputs: positive integer n, array of key S indexed from 1 to n.
  // the array S containing the keys in nondecreasing order.

  void merge2(int data[ ], int low, int mid, int high);
  // Problem: Merge the two sorted subarrays of S created in Mergesort 2.
  // Inputs: indices low, mid, and high, and the subarray of S indexed
  // from low to high. The keys in array slots from low to mid are already
  // sorted in nondecreasing order, as are the keys in array slots from
  // mid +1 to high.
  // Outputs: the subarray of S indexed from low to high containing the
  // keys in nondecreasing order.
}  
#endif

 

• sorting.cpp

// File: sorting.cpp
namespace algorithms
{
  void mergesort2(int data[ ], int low, int high)
  {
    int mid;

    if (low < high)
    {
      mid = (low + high) / 2;
      mergesort2(data, low, mid);
      mergesort2(data, mid+1, high);
      merge2(data, low, mid, high);
    }
  }

  void merge2(int data[ ], int low, int mid, int high)
  {
    int i, j, k;
    // A local array needed for the merging
    int* temp = new int[(high-low) + 1];

    i = low;
    j = mid + 1;
    k = 0;
    while (i <= mid && j <= high)
    {
      if (data[i] < data[j])
        temp[k] = data[i++]; // Copy from first half
      else
        temp[k] = data[j++]; // Copy from second half
      k++;
    }

    // Copy any remaining entries in the left and right subarrays.
    if (i > mid)
    {
      while (j <= high)
        temp[k++] = data[j++];
    }
    else
    {
      while (i <= mid)
        temp[k++] = data[i++];
    }

    // Copy from temp back to the data array, and release temp's memory.
    i = low;
    for (k = 0; k < (high-low) + 1 ; ++k)
      data[i++] = temp[k];

    delete [ ] temp;
  }
}

 

• sorttest.cpp

// File: sorttest.cpp
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include "sorting.h" // Provides sorting functions.
using namespace std;
using namespace algorithms;

// PROTOTYPE of a function that will test one of the sorting functions:
void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name);

void open_for_read(ifstream& f, const char filename[ ]);
// Postcondition: The ifstream f has been opened for reading using the given
// filename. If any errors occurred then an error message has been printed
// and the program has been halted.

bool is_more(istream& source);
// Precondition: input is an open istream.
// Postcondition: The return value is true if input still has more data to
// read; otherwise the return value is false.

void process_read(ifstream& f, int data[ ]);
// Precondition: input is an open istream.
// Postcondition: The values in inputfile are assigned to data array.

int main(int argc, char* argv[ ])
{  
  assert(argc == 2);
  testsort(mergesort2, argv[1], "mergesort");

  return EXIT_SUCCESS;
}

void testsort(void sorter(int data[ ], int start, int last),
              const char* file_name, const char* sorting_name)
{
  const int ARRAY_SIZE = 100000;
  int data[ARRAY_SIZE];
  ifstream infile;

  open_for_read(infile, file_name);
  process_read(infile, data);
  infile.close( );

  clock_t start, end;  
  cout << "Testing the " << sorting_name << endl;
  start = clock( );
  sorter(data, 0, ARRAY_SIZE-1); // Sort the numbers
  end = clock( );

  // Check the sorting result.
  for (int i = 1; i < ARRAY_SIZE; ++i)
  {
    if (data[i-1] > data[i])
      exit(0);
  }
  cout << "Sorting completed correctly." << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << sorting_name << "'s elpased time is : "<< result << " sec." << endl;
}

void open_for_read(ifstream& f, const char filename[ ])
{
  f.open(filename);

  if (f.fail( ))
  {
    cerr << "Could not open input file." << endl;
    exit(0);
  }
}

bool is_more(ifstream& source)
{
  return (source && source.peek( ) != EOF);
}

void process_read(ifstream& f, int data[ ])
{
  int index = 0;

  while (is_more(f))
  {
    assert(f);
    f >> data[index];
    ++index;
  }
}

 

 

Time Complexity Analysis

---

Basic operation

the comparison that takes place in merge

 

Input size

n, the number of items in the array S

 

Worst-Case Time Complexity

$\displaystyle W(n) = \underbrace{W(h)}_{\text{Time to sort U}} + \underbrace{W(m)}_{\text{Time to sort V}} + \underbrace{(h + m - 1)}_{\text{Time to merge}} = 2W(\frac{n}{2}) + n -1 \in \Theta(nlogn)$ 

 

$\displaystyle h = \frac{n}{2}​$
$\displaystyle m = n-h = n- \frac{n}{2} = \frac{n}{2} $
$\displaystyle h + m = \frac{n}{2} + \frac{n}{2} = n​$

 

👉 합병정렬은 퀵정렬과는 달리 정렬과정에서 추가적인 작업공간이 필요하다.  합병정렬의 장점은 시간복잡도가 최악인 경우의 비교횟수 마저도 O(nlogn)라는 점이다.