C++ • SORTING ALGORITHM Merge Sort

C++ • SORTING ALGORITHM

Merge Sort

ALGORITHM

Merge Sort

TIME COMPLEXITY

O(n log n)

SPACE COMPLEXITY

O(n)

ORDER

Ascending

C++ Implementation

merge_sort.cpp

#include <iostream>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

    // Helper function to merge two sorted halves
    void merge(int low, int mid, int high)
    {
        int temp[100];
        int left = low;
        int right = mid + 1;
        int k = 0;

        while (left <= mid && right <= high)
        {
            if (a[left] <= a[right])
            {
                temp[k++] = a[left++];
            }
            else
            {
                temp[k++] = a[right++];
            }
        }

        while (left <= mid)
        {
            temp[k++] = a[left++];
        }

        while (right <= high)
        {
            temp[k++] = a[right++];
        }

        for (int i = low; i <= high; i++)
        {
            a[i] = temp[i - low];
        }
    }

    // Helper recursive function for Merge Sort
    void mergeSortHelper(int low, int high)
    {
        if (low >= high) return;
        int mid = low + (high - low) / 2;
        mergeSortHelper(low, mid);
        mergeSortHelper(mid + 1, high);
        merge(low, mid, high);
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Merge Sort interface function
    void mergeSort()
    {
        mergeSortHelper(0, n - 1);
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.mergeSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes the input/output library required for cin and cout.

using namespace std;

Allows us to use standard C++ features without writing std:: repeatedly.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the number of elements in the array.

int a[100];

Declares an integer array capable of storing up to 100 elements.

void merge(...)

Merges two sorted sub-arrays into a single sorted range within a temporary array.

void mergeSortHelper(...)

Recursively divides the array into two halves until single elements remain.

int mid = low + ...

Finds the middle index of the current array range to prevent integer overflow.

ArraySort()

This is the class constructor. It runs automatically when the object is created.

n = 0;

Initializes the array length to zero.

void input()

Defines a function that accepts the array length and array elements from the user.

void mergeSort()

Public interface function that initiates the recursive merge sort process from index 0 to n - 1.

void output()

Defines the function that displays the sorted array.

ArraySort obj;

Creates an object named obj of the ArraySort class. The constructor runs automatically.

obj.input();

Calls the input function to read the array.

obj.mergeSort();

Calls the merge sort function to arrange the elements in ascending order.

obj.output();

Calls the output function to display the sorted array.

return 0;

Indicates that the program has completed successfully.

How merge sort works: It follows a Divide and Conquer approach. It recursively divides the array into two halves until each sub-array contains a single element, and then merges those sub-arrays back together in sorted order.