Thread: Merge Sort

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    3

    Merge Sort

    Please, how to make a merge sort program -in c++-which the user enters the numbers he wants to be sorted & then the program display the numbers after sorting.

    Or
    how to make modifications on the following program to do what iwant -enter numbers & then dispaly the sorted numbers.
    Code:
    void mergeSort(int numbers[], int temp[], int array_size=6)//
    {
    m_sort(numbers, temp, 0, array_size - 1);
    }
    
    
    
    void m_sort(int numbers[], int temp[], int left, int right)
    {
    int mid;
    
    if (right > left)
    {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);
    
    merge(numbers, temp, left, mid+1, right);
    }
    }
    
    
    void merge(int numbers[], int temp[], int left, int mid, int right)
    {
    int i, left_end, num_elements, tmp_pos;
    
    left_end = mid - 1;
    tmp_pos = left;
    num_elements = right - left + 1;
    
    while ((left <= left_end) && (mid <= right))
    {
    if (numbers[left] <= numbers[mid])
    {
    temp[tmp_pos] = numbers[left];
    tmp_pos = tmp_pos + 1;
    left = left +1;
    }
    else
    {
    temp[tmp_pos] = numbers[mid];
    tmp_pos = tmp_pos + 1;
    mid = mid + 1;
    }
    }
    
    while (left <= left_end)
    {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
    }
    while (mid <= right)
    {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
    }
    
    for (i=0; i <= num_elements; i++)
    {
    numbers[right] = temp[right];
    right = right - 1;
    }
    }

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Show us what you have tried and we will help you.

    To me this sounds an aweful lot like homework.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    3

    It was homework but

    May be it was homework but the problem for me was misunderstanding the recursion
    but now i undestand it
    .


    I have made little modification on program in order to make what iwant-it's completed.

    Code:
    #include<iostream.h>
    #include <stdlib.h>
    
    void m_sort(int numbers[], int temp[], int left, int right);
    void merge(int numbers[], int temp[], int left, int mid, int right);
    
    
    void main()
    {
      int i;
      int *numbers;
      int *temp;
      int len;  
     
      cout<<"How many numbers do you want to sort??"<<endl;
      cin>>len;
    
      numbers=new int[len];
      temp=new int[len];
    
      for (i = 0; i < len; i++)
      {
    	  cout<<"Enter number"<<i+1<<endl;
    	  cin>>numbers[i]; 
      }
    
      //perform merge sort on array
      m_sort(numbers, temp, 0, len - 1);
    
      cout<<"Done with sort"<<endl;
    
      for (i = 0; i < len; i++)
        cout<<numbers[i]<<endl;
    }
    
    void m_sort(int numbers[], int temp[], int left, int right)
    {
      int mid;
    
      if (right > left)
      {
        mid = (right + left) / 2;
        m_sort(numbers, temp, left, mid);
        m_sort(numbers, temp, mid+1, right);
    
        merge(numbers, temp, left, mid+1, right);
      }
    }
    
    
    void merge(int numbers[], int temp[], int left, int mid, int right)
    {
      int i, left_end, num_elements, tmp_pos;
    
      left_end = mid - 1;
      tmp_pos = left;
      num_elements = right - left + 1;
    
      while ((left <= left_end) && (mid <= right))
      {
        if (numbers[left] <= numbers[mid])
        {
          temp[tmp_pos] = numbers[left];
          tmp_pos = tmp_pos + 1;
          left = left +1;
        }
        else
        {
          temp[tmp_pos] = numbers[mid];
          tmp_pos = tmp_pos + 1;
          mid = mid + 1;
        }
      }
    
      while (left <= left_end)
      {
        temp[tmp_pos] = numbers[left];
        left = left + 1;
        tmp_pos = tmp_pos + 1;
      }
      while (mid <= right)
      {
        temp[tmp_pos] = numbers[mid];
        mid = mid + 1;
        tmp_pos = tmp_pos + 1;
      }
    
      for (i=0; i < num_elements; i++)
      {
        numbers[right] = temp[right];
        right = right - 1;
      }
    }

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