Thread: Merge Sort Help

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    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.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    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 .

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Last edited by Stoned_Coder; 05-14-2005 at 12:08 PM.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    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.

  6. #6
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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;
    }
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort the best sorting algorithm?
    By sehr alt in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 06-20-2007, 02:19 PM
  2. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 11:14 AM
  3. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  4. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM
  5. merge sort
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-02-2001, 06:58 PM