Merge Sort Help

Hello I havent begun to code merge sorth because I am still trying to understand how the algorithm works. This is what I know from browsing around the net:

"MergeSort is a recursive sorting procedure that uses O(n log n) comparisons in the worst case. To sort an array of n elements, we perform the following three steps in sequence:

If n<2 then the array is already sorted. Stop now.
Otherwise, n>1, and we perform the following three steps in sequence:

Sort the left half of the the array.

Sort the right half of the the array.

Merge the now-sorted left and right halves."

So my question is how do I sort each halve? Do i employ another sorting algorithm to do it? Any clarification is appreciated.

yes thats right. to merge sort i usually use std::sort or qsort() on each half of the array. this gives you two sorted arrays. you then merge them. to do this you compare the first element of each array and take the lowest(or highest depends) and pop it in a new array. then increase the index for the array you just removed an element for and continue till both arrays empty.

I dont think I can use another sorting algorithm, I think I have to break down the initial array into a bunch of subarrays of one element, which are already sorted of course. Then merge everything back using the method you just described. Cause if i employ qsort thats using another algorithm. Basically the point of this project is to compare a bunch of sorting algorithms. Thanks for replying :).

nothing stopping you from writing your own qsort algorithm for instance. the merge in merge sort is putting the two SORTED arrays into one. if the arrays are not sorted you cannot merge.

Oh i see you have to do this recursively. Well you have to constantly split the arrays until you have arrays of 1 length then merge them.

Ok I was able to recursively split the index of the array here is the code:

Code:

---

// This is the main project file for VC++ application project
// generated using an Application Wizard.

#include "stdafx.h"

#using <mscorlib.dll>

using namespace System;

void fillA(Int32[], int);
void printA(Int32[]);
int split(Int32 []);


int _tmain()
{
        Console::Write(S"Input N:");
        int n= Int32::Parse(Console::ReadLine());
        Int32 x[]= new Int32[n];
                fillA(x,100);
                printA(x);
                mergeSort(x)

               
        return 0;
}
void fillA(Int32 d[], int v){
Random *r= new Random();
        for(int i=0; i != d->Length; i++)
                d[i]=r->Next(1,v);
}
void printA(Int32 d[]){
        for(int i=0; i != d->Length; i++)
               
        Console::Write(S"{0} \t",d[i].ToString());
        Console::WriteLine();
}

void mergeSort(Int 32 a[]){

split(a, 0, a->Length -1);

}



void split(Int32 a[],low, high) {
       
        if(high > low){
               
        int mid = (high + low)/2;
        split(a,low,mid);
        split(a,mid+1,high);
        combine(a,low, mid+1,high)       
        }

}

---

The split function will split indexes until you have a single index remaining. That is, an array of 3 elements will be broken down to o,1,2. Now I dont know how to compare the values at the indexes and sort them. Am i supposed to be doing this while i am splitting? Please any hints and suggestions are most welcome.

here this should help. study it.

Code:

---

#include <iostream>

using namespace std;

void merge(int A[],int bottom,int centre,int top)
{
    int temp[20];
    int left_index=bottom;
    int right_index=centre+1;
    int temp_index=bottom;
    while(left_index<=centre && right_index<=top)
    {
      if(A[left_index]<=A[right_index])
      {
          temp[temp_index]=A[left_index];
          left_index++;
      }
      else
      {
          temp[temp_index]=A[right_index];
          right_index++;
      }
      temp_index++;
    }
    if(left_index>centre)
    {
      for(int i=right_index;i<=top;i++)
      {
          temp[temp_index]=A[i];
          temp_index++;
      }
    }
    else
    {
      for(int i=left_index;i<=centre;i++)
      {
          temp[temp_index]=A[i];
          temp_index++;
      }
    }
    for(int i=bottom;i<=top;i++) A[i]=temp[i];
}

void mergesort(int A[],int bottom, int top)
{
  if(bottom<top)
  {
      int centre=(bottom+top)/2;
      mergesort(A,bottom,centre);
      mergesort(A,centre+1,top);
      merge(A,bottom,centre,top);
    }
}

int main()
{
  int A[20];
  int bottom,top,num;
  cout<<"Enter the num elements ( Max 20 ):-"<<endl;
  cin>>num;
  cout<<"Enter the elements separated by space :-"<<endl;
  for (int i=0;i<num;i++) cin>>A[i];
  cout<<"Elements in order entered are...."<<endl;
  for (int i=0;i<num;i++) cout<<A[i]<<" ";
  cout<<endl<<endl;
  bottom=0;
  top=num-1;
  mergesort(A,bottom,top);
  cout<<"Sorted by mergesort into ascending order ...."<<endl;
  for(int i=bottom;i<=top;i++) cout<<A[i]<<" ";
  cout<<endl<<endl;
  return 0;
}

---