Simple Merge Sort Program in C++

About this program

This is an example program in sorting programs. Read the concept first: Understanding Array in C++, then study the code and output below.

Definition

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Conceptually, a merge sort works as: Divide the unsorted list into n sublists, each containing 1 element and repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Simple Merge Sort Program Example

/* Simple Merge Sort Program Using Functions and Array in C++*/
/* Data Structure C++ Programs,C++ Functions and Array Examples */

#include <iostream>
#include<conio.h>
#include<stdlib.h>

#define MAX_SIZE 5

using namespace std;

void merge_sort(int, int);
void merge_array(int, int, int, int);

int arr_sort[MAX_SIZE];

int main() {
    int i;

    cout << "Simple C++ Merge Sort Example - Functions and Array\n";
    cout << "\nEnter " << MAX_SIZE << " Elements for Sorting : " << endl;
    for (i = 0; i < MAX_SIZE; i++)
        cin >> arr_sort[i];

    cout << "\nYour Data   :";
    for (i = 0; i < MAX_SIZE; i++) {
        cout << "\t" << arr_sort[i];
    }

    merge_sort(0, MAX_SIZE - 1);

    cout << "\n\nSorted Data :";
    for (i = 0; i < MAX_SIZE; i++) {
        cout << "\t" << arr_sort[i];
    }

    getch();

}

void merge_sort(int i, int j) {
    int m;

    if (i < j) {
        m = (i + j) / 2;
        merge_sort(i, m);
        merge_sort(m + 1, j);
        // Merging two arrays
        merge_array(i, m, m + 1, j);
    }
}

void merge_array(int a, int b, int c, int d) {
    int t[50];
    int i = a, j = c, k = 0;

    while (i <= b && j <= d) {
        if (arr_sort[i] < arr_sort[j])
            t[k++] = arr_sort[i++];
        else
            t[k++] = arr_sort[j++];
    }

    //collect remaining elements 
    while (i <= b)
        t[k++] = arr_sort[i++];

    while (j <= d)
        t[k++] = arr_sort[j++];

    for (i = a, j = 0; i <= d; i++, j++)
        arr_sort[i] = t[j];
}

Sample Output

Simple Merge Sort Example - Functions and Array

Enter 5 Elements for Sorting
67
57
45
32
13

Your Data   :   67      57      45      32      13

Sorted Data :   13      32      45      57      67

------------------
(program exited with code: 0)

Related Pages

Learn the concept first, then study the code:

• Data Structures — Browse all Data Structures.
• Understanding Array in C++ — Tutorial — arrays underpin sorting algorithms.
• Simple Bubble Sort Program in C++ — More in sorting programs.
• Simple Bubble Sort Program using functions in C++ — More in sorting programs.