Question

Implement Merge Sort and test it on a small list of 10 random integer values. c++ please

template            // merge-sort S
void mergeSort(list& S, const C& less) {
typedef typename list::iterator Itor;       // sequence of elements
int n = S.size();
if (n <= 1) return;                   // already sorted
list S1, S2;
Itor p = S.begin();
for (int i = 0; i < n / 2; i++) S1.push_back(*p++);   // copy first half to S1
for (int i = n / 2; i < n; i++) S2.push_back(*p++);   // copy second half to S2
S.clear();                       // clear S's contents
mergeSort(S1, less);               // recur on first half
mergeSort(S2, less);               // recur on second half
merge(S1, S2, S, less);               // merge S1 and S2 into S
}

template
class Merge {                       // generic Merge
public:                        // global types
typedef std::list List;               // list type
void merge(List& A, List& B, List& C);       // generic merge function
protected:                        // local types
typedef typename List::iterator Itor;       // iterator type
// overridden functions
virtual void fromA(const E& a, List& C) = 0;
virtual void fromBoth(const E& a, const E& b, List& C) = 0;
virtual void fromB(const E& b, List& C) = 0;
};

template                // generic merge
void Merge::merge(List& A, List& B, List& C) {
Itor pa = A.begin();               // A's elements
Itor pb = B.begin();               // B's elements
while (pa != A.end() && pb != B.end()) {       // main merging loop
if (*pa < *pb)
fromA(*pa++, C);               // take from A
else if (*pa == *pb)
fromBoth(*pa++, *pb++, C);           // take from both
else
fromB(*pb++, C);               // take from B
}
while (pa != A.end()) { fromA(*pa++, C); }       // take rest from A
while (pb != B.end()) { fromB(*pb++, C); }       // take rest from B
}

Answer 1

#include <iostream>

void PrintArray(int *array, int n) {

  for (int i = 0; i < n; ++i)

    std::cout << array[i] << " " << std::flush;

  std::cout << std::endl;

}

void Merger(int arr[], int lo, int  mi, int hi){

    int *temp = new int[hi-lo+1];//temporary merger array

    int i = lo, j = mi + 1;//i is for left-hand,j is for right-hand

    int k = 0;//k is for the temporary array

    while(i <= mi && j <=hi){

        if(arr[i] <= arr[j])

            temp[k++] = arr[i++];

        else

            temp[k++] = arr[j++];

    }

    //rest elements of left-half

    while(i <= mi)

        temp[k++] = arr[i++];

    //rest elements of right-half

    while(j <= hi)

        temp[k++] = arr[j++];

    //copy the mergered temporary array to the original array

    for(k = 0, i = lo; i <= hi; ++i, ++k)

        arr[i] = temp[k];

    delete []temp;

}

void MergeSortHelper(int arr[], int lo, int hi){

    int mid;

    if(lo < hi){

        mid = (lo + hi) >> 1;

        MergeSortHelper(arr, lo, mid);

        MergeSortHelper(arr, mid+1, hi);

        Merger(arr, lo, mid, hi);

    }

}

void MergeSort(int arr[], int arr_size){

    MergeSortHelper(arr, 0, arr_size-1);

}

int main() {

  int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};

  int n = sizeof(array)/sizeof(array[0]);

  std::cout << "Before Merge Sort :" << std::endl;

  PrintArray(array, n);

  MergeSort(array, n);

  std::cout << "After Merge Sort :" << std::endl;

  PrintArray(array, n);

  return (0);

}

/*

OUTPUT

Before Merge Sort :

94 42 50 95 333 65 54 456 1 2325

After Merge Sort :

1 42 50 54 65 94 95 333 456 2325

*/