Merge Sort Using C++

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;
}