0

I currently have this code that performs Merge sort (not completed yet) and I was wondering if anyone knows how to do it without recursion. the part I am stuck at is the part where I have to keep on creating new sub-arrays after each split. For example, if I have an array of length 8:

I would need 2 arrays for the initial split into 4 and 4 and then when I would have to split again into 2 2 2 2 which means I need 4 more arrays.. and so on. How do I accomplish this without recursion?

So far I got to the first split in my code:

void merge_sort(int arr[], int len) // len = 10, array of 10
{
    int i;
    int *firsthalf;
    int *secondhalf;
    int firsthalf_elements, secondhalf_elements;

    if (len<2)
    {
        return;
    }

    firsthalf_elements = len/2;
    secondhalf_elements = len - firsthalf_elements;
    firsthalf = (int*)malloc(sizeof(int) * n1);
    secondhalf = (int*)malloc(sizeof(int) * n2);
    for (i =0; i < firsthalf_elements; i++) 
    {
        firsthalf[i] = arr[i];
    }
    for (i = 0; i < secondhalf_elements; i++) 
    {

        secondhalf[i] = arr[i+firsthalf_elements];
    }

    //Normally over here we would make a recursive call, but i want to do this w/o recursion.
BeginnerC
  • 119
  • 2
  • 14
  • 3
    Have you checked out this answer? [http://stackoverflow.com/questions/1557894/non-recursive-merge-sort](http://stackoverflow.com/questions/1557894/non-recursive-merge-sort) – John Odom Nov 07 '14 at 19:53
  • Unfortunately I don't understand it that well, it looks like a different lgoic than what I have done in my code. – BeginnerC Nov 07 '14 at 19:55
  • [Don't cast the result of malloc (and friends)](http://stackoverflow.com/q/605845). – Deduplicator Nov 07 '14 at 19:56
  • You are making a curious start to a not-in-place recursive merge-sort. Of course non-recursive in-place looks different. – Deduplicator Nov 07 '14 at 19:58
  • I would like to clarify though, would I have to keep making new arrays at each split, or am I thinking of this wrong? – BeginnerC Nov 07 '14 at 19:59
  • Instead of dividing the array in half and recursing, the "other way" is to go through the array and sort each subarray of 2 elements (0-1, 2-3, 4-5, ...). Then make another pass, but now sort each subarray of 4 elements (0-3, 4-7, 8-11, ...). Now make another pass but with subarrays of size 8 elements, etc, until you can sort the whole array in the last pass. Each time you sort the subarrays, you know that it is composed of 2 sorted smaller subarrays. For example, if you are sorting subarray 0..7, you know that you've already sorted 0..3 and 4..7 so you just need to do a merging operation. – JS1 Nov 07 '14 at 20:00
  • The main part IO am confused about is how to keep making new arrays to store the split elements. – BeginnerC Nov 07 '14 at 20:05
  • You could allocate one big temp array at first (as big as your initial array). Then when you merge two subarrays, you can copy them to the temp array and then copy elements back to the original array. – JS1 Nov 07 '14 at 20:27
  • @JS1 the more commonly used algorithm is to sort from a "source" array to a "target" array, and toggle which is source and which is target with each loop progression. There will be one final mass-copy if the log2 of the original source is odd. Doing this will *significantly* reduce the number of copies performed. – WhozCraig Nov 07 '14 at 20:31
  • @WhozCraig I know but try explaining that to someone who is already so confused. – JS1 Nov 07 '14 at 21:11

0 Answers0