Merge Sort Using C++

Link Copied To Clipboard !

Algorithms

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

Merge Sort Using C++



#include<iostream>
using namespace std;

class List{
    private:
        int* arr;
        int len;

        void merge(int lower, int mid, int upper){
            int leftSize = mid - lower + 1; //mid inclusive
            int rightSize = upper - mid; //mid exclusive
            int* leftArr = new int[leftSize];
            int* rightArr = new int[rightSize];

            for(int i = 0; i < leftSize; i++){
                *(leftArr + i) = *(this->arr + lower + i); //mid inclusive
            }
            for(int i = 0; i < rightSize; i++){
                *(rightArr + i) = *(this->arr + mid + 1 + i); //mid exclusive
            }

            int i = 0, j = 0, k = lower;
            while(i < leftSize && j < rightSize){
                if(*(leftArr + i) <= *(rightArr + j)){
                    *(arr + k) = *(leftArr + i);
                    i++;
                }else{
                    *(arr + k) = *(rightArr + j);
                    j++;
                }
                k++;
            }

            //copy remaining items
            while(i < leftSize){
                *(arr + k) = *(leftArr + i);
                i++;
                k++;
            }

            while(j < rightSize){
                *(arr + k) = *(rightArr + j);
                j++;
                k++;
            }
        }

    public:
        List(){
            this->arr = NULL;
            this->len = 0;
        }

        void populate(){
            do{
                cout<<"enter the size:"<<endl;
                cin>>this->len;
            }while(this->len < 0);

            this->arr = new int[this->len];

            for(int i = 0; i < this->len; i++){
                cout<<"enter "<<i<<"th item"<<endl;
                cin>>*(arr+i);
            }
        }

        void mergeSort(int lower, int upper){
            if(lower < upper){
                int mid = (lower + upper) / 2;
                mergeSort(lower, mid);
                mergeSort(mid + 1, upper);
                merge(lower, mid, upper);
            }
            
        }

        int length(){
            return len;
        }

        void display(){
            if(arr == NULL){
                cout<<"list is empty !"<<endl;
                return;
            }
            cout<<"[";
            for(int i = 0; i < this->len; i++){
                if(i != len-1){
                    cout<<*(arr+i)<<", ";
                }else{
                    cout<<*(arr+i);
                }
            }
            cout<<"]"<<endl;
        }

        ~List(){
            delete arr;
        }
};

int main(){
    List list;
    list.populate();
    cout<<"unsorted list:";
    list.display();
    cout<<"sorted list:";
    list.mergeSort(0, list.length()-1);
    list.display();
    return 0;
}


You May Also Like