CODEWITHSUNDEEP
c#arrayssortingrecursionmergesort
Hoppe
Hoppe

Reputation: 6815

Simple merge sort not recursing through array correctly

I’m trying to port the simple merge sort algorithm found here to C# as an academic exercise. I believe that I followed their code, but the recursive condition is wrong.

I believe that I’m correctly recursing down the left side of the tree(?), but then when I get to the second half, it enters an infinite loop. How do I get the recursion to continue processing the array?

When I get to the second half, the output is: 

11, 1, 5 
11, 1, 3 
11, 1, 2 
11, 1, 1 
11, 4, 6
11, 4, 6 
11, 4, 6 
11, 4, 6

The code is:

var input = new[] {5, 10, 1, 7, 9, 15, 8, 11, 20, 2};
var result = MergeSort.Sort(input);

using System;
using System.Diagnostics;

namespace MergeSort {
    internal class MergeSort
    {    
        public static int[] Sort(int[] input, int left = 0, int? rightNullable = null)
        {
            var right = (rightNullable == null)
                ? input.Length - 1
                : Convert.ToInt32(rightNullable);

            if (left >= right) { return input; }

            decimal centerDcl = left + Convert.ToInt32(right)/2;
            var center = Convert.ToInt32(centerDcl);

            Console.WriteLine("{0}, {1}, {2}", input.Length + 1, left + 1, center + 1);
            Debug.WriteLine("{0}, {1}, {2}", input.Length + 1, left + 1, center + 1);

            Sort(input, left, center);
            Sort(input, center + 1, rightNullable);

            input = Merge(input, left, center + 1, right);

            return input;
        }

Upvotes: 0

Views: 174

Answers (1)

Erti-Chris Eelmaa
Erti-Chris Eelmaa

Reputation: 26338

decimal centerDcl = left + Convert.ToInt32(right)/2;

this does not seem right.

It should be:

decimal centerDcl = (left + Convert.ToInt32(right))/2;

Upvotes: 1

Related Questions