0

To keep it short. I made a MergeSort, which should sort an int[]. To test the MergeSort I made an array containing 4 integers in random order. It returns the exact list in the order given to the MergeSort, instead of doing what it should do. I wonder what I did wrong.

Edit: The first two merges return these two lists: 4, 15 && 5, 16, however the last merge doesn't work.

This is the actual code:

 public static int[] Merge(int[] list, int left, int mid, int right)
    {
        int[] returnList = new int[list.Length];
        int Index = left;

        //last value of left half
        int leftEnd = mid;

        //both the left side and right side contain atleast one value
        while (leftEnd >= left && right >= (mid + 1))
        {
            if (list[left] <= list[(mid + 1)])
            {
                returnList[Index] = list[left];
                left++;
            }
            else
            {
                returnList[Index] = list[(mid + 1)];
                mid++;
            }
            Index++;
        }

        //right side is empty, left contains atleast one value
        while (leftEnd >= left)
        {
            returnList[Index] = list[left];
            left++;
            Index++;
        }

        //left side is empty, right contains atleast one value
        while (right >= (mid + 1))
        {
            returnList[Index] = list[(mid + 1)];
            mid++;
            Index++;
        }

        return returnList;
    }

    public static int[] Split(int[] list, int left, int right)
    {
        if (right > left)
        {
            int mid = (right + left) / 2;

            Split(list, left, mid); //first half
            Split(list, (mid + 1), right); //second half
            list = Merge(list, left, (mid + 1), right);
        }

        return list;
    }

My Main:

        int[] intArray = new int[] { 12, 4, 16, 5 };
        int[] ReturnTest = MergeSort.Split(intArray, 0, intArray.Length - 1);

        foreach (int value in ReturnTest)
        {
            Console.WriteLine(value);
        }

The expected output: 4, 5, 12, 16

The actual output: 12, 4, 16, 5

M. Mayhem
  • 39
  • 7
  • What wrong with `Array.Sort(intArray);` ? – Jim Dec 05 '16 at 01:23
  • I'm a college student and we've been asked to write a MergeSort ourselves. – M. Mayhem Dec 05 '16 at 01:25
  • You did not give the expected and actual output. – Lei Yang Dec 05 '16 at 01:27
  • @M.Mayhem Ah ok :-) , there is no shame in mentioning that. Otherwise I would already bet, some will say "don't reinvent the wheel" ;-) – Jim Dec 05 '16 at 01:28
  • 11
    https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ - As a student this is an excellent opportunity for you to familiarize yourself with the use of a debugger. Step through the code, line by line, as it executes and observe the runtime behavior and variable values. There you can determine exactly where the behavior deviates from what you expect. – David Dec 05 '16 at 01:28
  • Thanks for the comments! And will try, @David! – M. Mayhem Dec 05 '16 at 01:31
  • How about a good old bubble sort? http://stackoverflow.com/questions/14768010/simple-bubble-sort-c-sharp – Mark Kram Dec 05 '16 at 02:05
  • @David I tried the MergeSort with an array of 4 numbers, however in the 3rd merge (the final merge) the list is not the array of the the first 2 merges merged together, but the actual starting input array. I'm not sure how to fix this. – M. Mayhem Dec 05 '16 at 03:02
  • @M.Mayhem does not the referred article answer that question though? Just use a debugger and step through your code. – zerkms Dec 05 '16 at 03:25

0 Answers0