Click here to Skip to main content
15,891,864 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
I want to wright programm for three way merge sort by using two way,with minimum time complexity

What I have tried:

C++
#include <stdio.h>
#define max 10

int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];

void merging(int low, int mid1,int mid2, int high) {
   int l1, l2,l3, i;

  for(l1 = low, l2 = mid1 + 1,l3=mid2+1,i = low; l1 <= mid1 && l2 <= mid2,l3<=high; i++)
      {
      if((a[l1] <= a[l2])&&(a[l1]<=a[l3]))
         b[i] = a[l1++];
      else if((a[l2]<=a[l1])&&(a[l2]<=a[l3]))
         b[i] = a[l2++];
        else b[i]=a[l3++];
   }
   
   while(l1 <= mid1)    
      b[i++] = a[l1++];

   while(l2 <= mid2)   
      b[i++] = a[l2++];
   
   while(l3<=high)
      b[i++]=a[l3++];

   for(i = low; i <= high; i++)
      a[i] = b[i];
}

void sort(int low, int high) {
   int mid1,mid2;
   
   if(low < high) {
      mid1 = (low + high) / 3;
      mid2=2*(low+high)/3;
      sort(low, mid1);
      sort(mid1+1,mid2);
      sort(mid2+1, high);
      merging(low, mid1,mid2, high);
   } else { 
      return;
   }   
}

int main() { 
   int i;

   printf("List before sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);

   sort(0, max);

   printf("\nList after sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}
Posted
Updated 8-Jan-18 11:19am
v2

Then you have our permission.
But ... since this is your homework, you are expected to do it yourself, noit get us to "fix it" for you.

So, its going to be up to you.
Fortunately, you have a tool available to you which will help you find out what is going on: the debugger. How you use it depends on your compiler system, but a quick Google for the name of your IDE and "debugger" should give you the info you need.

Put a breakpoint on the first line in the function, and run your code through the debugger. Then look at your code, and at your data and work out what should happen manually. Then single step each line checking that what you expected to happen is exactly what did. When it isn't, that's when you have a problem, and you can back-track (or run it again and look more closely) to find out why.

Sorry, but we can't do that for you - time for you to learn a new (and very, very useful) skill: debugging!
 
Share this answer
 
It would require a lot of time to check your code for errors and if it would do what it should.

But there is one obvious error:
Your b array is too small resulting in a buffer overrun. It must have the same size of 11 (max + 1) as the a array.
 
Share this answer
 
It looks you modified this program: Merge Sort Program in C[^]. It looks, also, that straight modification doesn't work. I think the merging function is flawed. You should possibly inspect its algorithm and fix it.
 
Share this answer
 
C++
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };

Advice: do not start with a sorted array as input, never.

I fear your code do not take into account all details of a 'three way merge sort'. When you are done with 1 of the 3 subarrays, how do you know the order or the 2 remaining subarrays?

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900