The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Sorting

Problem :-
Implement the Merge sort algorithm.

Solution :-
Merge sort is a divide & conquer algorithm which works by dividing the array of elements into sub-arrays, sorting the subarrays and then merging the sorted sub-arrays to produce final sorted array.
Consider an unsorted array of size n. First the unsorted array is divided into n sub-arrays ( each array of size 1 ) [ an array of size 1 is by default sorted ].
Merge the two adjacent sorted sub-arrays and repeat the steps of sorting & merging sub-arrays until only one sub-array remains and that is the final sorted array. Complexity of the algorithm is O(n log n).
Consider the following array { 7, 2, 5, 3, 1, 8, 4, 6 }. Let's see how Merge sort technique works :-

{ 7 } | { 2 } | { 5 } | { 3 } | { 1 } | { 8 } | { 4 } | { 6 } ( Array is divided into 8 sub-arrays of size 1 )

First Merge :-
{ 2, 7 } | { 3, 5 } | { 1, 8 } | { 4, 6 } ( Merge the adjacent sorted sub-arrays of size 1 )

Second Merge :-
{ 2, 3, 5, 7 } | { 1, 4, 6, 8 } ( Merge the adjacent sorted sub-arrays of size 2 )

Third Merge :-
{ 1, 2, 3, 4, 5, 6, 7, 8 } ( Merge the adjacent sorted sub-arrays of size 4 )

Now, we have only one sub-array of size n, which is the final sorted array.

#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
   int i;
   for (i=0;i<size;i++) {
      cout<<arr[i]<<" ";
   }
}

// merge 2 halves of arr[start_idx...mid_idx] and 
// arr[mid_idx+1...start_idx] into arr[]
void merge(int arr[],int start_idx, int mid_idx, int end_idx) {
   int i,j,k;
   int size1 = mid_idx - start_idx + 1;
   int size2 = end_idx - mid_idx;

   // temporary arrays
   int left[size1];
   int right[size2];

   // copy data from original array into temporay arrays
   for (i=0;i<size1;i++) {
      left[i] = arr[start_idx+i];
   }
   for (j=0;j<size2;j++) {
      right[j] = arr[mid_idx+1+j];
   }

   // merge the temporary arrays back to original array
   // s.t the original array becomes sorted
   i = 0; j = 0; k = start_idx;
   while (i < size1 &&  j < size2) {
      if (left[i] < right[j]) {
         arr[k] = left[i];
         i++;
      }
      else {
         arr[k] = right[j];
         j++;
      }
      k++;
   }

   // copy remaining elements of left[], if any
   while (i < size1) {
      arr[k] = left[i];
      i++;
      k++;
   }

   // copy remaining elements of right[], if any
   while (j < size2) {
      arr[k] = right[j];
      j++;
      k++;
   }
}

// merge sort the array recursively
// divide and conquer
void mergeSort(int arr[], int start_idx, int end_idx) {
   int mid_idx;
   if (start_idx < end_idx) {
      mid_idx = (start_idx + end_idx) / 2;
      // mergesort the two halves of array first
      mergeSort(arr, start_idx, mid_idx);
      mergeSort(arr, mid_idx+1, end_idx);
      // merge the two halves
      // merged array is sorted
      merge(arr,start_idx, mid_idx, end_idx);
   }
}

// main
int main() {
   int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :: ";
   displayArray(arr,size);
   mergeSort(arr,0,size-1);
   cout<<"\nSorted Array   :: ";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Sorting
* Implement the Bubble Sort algorithm
* Implement the Selection Sort algorithm
* Implement the Insertion Sort algorithm
* Implement the Merge Sort algorithm
* Implement the Quick Sort algorithm