Why does my merge sort algorithm not sort my array correctly?

Question

I am currently triyng to sort some intergers with Merge Sort, but something is wrong with my algoritm. I have a larger file with integers Im supposed to sort, but I use a smaller, given array to check if its working before sorting the larger file.

My Output from THIS algoritm is: 1 2 2 2 4 5 6, but it's supposed to be: 1 2 4 5 6 9 10 ??

Here's what I've got:

private static int[] data = new int[] { 1, 9, 10, 2, 4, 5, 6 };

static void Main(string[] args)
{
   int N = data.Length;
   Sort(data, 0, N - 1);
   for (int i = 0; i < N; i++)
       Console.WriteLine(data[i]);
}

private static void Merge(int[] intArray, int lo, int mid, int hi)
{
   int i = lo;
   int j = mid + 1;
   if (intArray.Length != 0)
       for (int k = lo; k <= hi; k++)
           data[k] = intArray[k];
   for (int k = lo; k <= hi; k++)
   {
       if (i > mid)
           intArray[k] = data[j++];
       else if (j > hi)
           intArray[k] = data[i++];
       else if (data[j] < data[i])
           intArray[k] = data[j++];
       else if (data[i] < data[j])
           intArray[k] = data[i++];
   }
}

private static void Sort(int[] intArray, int lo, int hi)
{
   if (hi <= lo)
       return;
   int mid = lo + (hi - lo) / 2;
   Sort(intArray, lo, mid);
   Sort(intArray, mid + 1, hi);
   Merge(intArray, lo, mid, hi);
}

data[k] = intArray[k]; -- data and intArray are the same array, so this line does nothing (it's exactly the same as data[k] = data[k], because intArray points to the same array as data. I suspect your problems come from this misunderstanding of how C# reference types work. — canton7
– canton7, Commented Oct 4, 2019 at 11:31
Thank you for your reply! The only thing I want the achieve in that part, is that if there's only 1 or less elements in the array, theres nothing more to sort. Then it should be the very same array. If i comment out that whole if statement with the for-loop, the output is still the same. — Emsko
– Emsko, Commented Oct 4, 2019 at 11:46

AbdelAziz AbdelLatef · Accepted Answer · 2019-10-04 12:28:29Z

2

I think the problem is in array reference in C# as @canton7 said, try this code:

private static int[] data = new int[] { 1, 9, 10, 2, 4, 5, 6 };
private static int[] intArray;

static void Main()
{
    int N = data.Length;
    intArray = new int[N];
    Sort(0, N - 1);
    for (int i = 0; i < N; i++)
        Console.WriteLine(intArray[i]);
}

private static void Merge(int lo, int mid, int hi)
{
    int i = lo;
    int j = mid + 1;      
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid)
            intArray[k] = data[j++];
        else if (j > hi)
            intArray[k] = data[i++];
        else if (data[j] < data[i])
            intArray[k] = data[j++];
        else if (data[i] < data[j])
            intArray[k] = data[i++];
    }
    if (intArray.Length != 0)
        for (int k = lo; k <= hi; k++)
            data[k] = intArray[k];
}

private static void Sort(int lo, int hi)
{
    if (hi == lo)
        return;
    int mid = lo + (hi - lo) / 2;
    Sort(lo, mid);
    Sort(mid + 1, hi);
    Merge(lo, mid, hi);
}

edited Oct 4, 2019 at 12:28

answered Oct 4, 2019 at 12:19

AbdelAziz AbdelLatef

3,7527 gold badges28 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Emsko Over a year ago

Thank you very much! That helped me a lot. It is now working perfectly. Really appreciate it!

AbdelAziz AbdelLatef Over a year ago

You are welcome, just avoid dealing with arrays in C# as they will be copied between methods. This doesn't happed unfortunately.

Collectives™ on Stack Overflow

Why does my merge sort algorithm not sort my array correctly?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related