merge sort implementation query

Question

I found this example of a merge sort algorithm online on a tutorial webpage and I have been trying to understand ow the code implements the algorithm. The example i found uses recursion and a temporary array to sort the array of unsorted algorithms. My query is in the final step of the process. When copying the elements of the temporary array into the original array to sort the array. why does the algorithm decrements the right attribute instead of incrementing the left attribute? when i incremented the left left value the algorithm does not work.

class Assignment1
{
    static void Main(string[] args)
    {
        Console.WriteLine("Size of array:");
        int n = Convert.ToInt16(Console.ReadLine());
        int[] unsorted = new int[n];

        for(int i = 0; i < n; i++)
        {
            Console.WriteLine("Enter a number:");
            unsorted[i] = Convert.ToInt16(Console.ReadLine());
        }

        Console.WriteLine("--------Sort---------");

        Recursion_Sort(unsorted, 0, n - 1);
        for (int i = 0; i < n; i++)
        {
              Console.WriteLine(unsorted[i]);
        }
    }

    static public void Merge(int[] numbers, int left, int mid, int right, int n)
    {

        int[] tempArray = new int[n];

        int i, lEnd, size, pos;



        lEnd = mid - 1;
        pos = left;
        size = (right - left + 1);


        while ((left <= lEnd) && (mid <= right))
        {

            if (numbers[left] <= numbers[mid])
            {

                tempArray[pos] = numbers[left];
                pos++;
                left++;
            }

            else
            {

                tempArray[pos] = numbers[mid];
                pos++;
                mid++;
            }
        }



        while (left <= lEnd)
        {
            tempArray[pos] = numbers[left];
            pos++;
            left++;
        }


        while (mid <= right)
        {
            tempArray[pos] = numbers[mid];
            pos++;
            mid++;
        }
        Console.WriteLine(tempArray.Length);


        for (i = 0; i < size; i++)
        {
            numbers[right] = tempArray[right];
            right--;
        }
    }

    static public void Recursion_Sort(int[] numbers, int left, int right)
    {

        int mid;

        if (right > left)
        {
            mid = (right + left) / 2;


            Recursion_Sort(numbers, left, mid);
            Recursion_Sort(numbers, (mid + 1), right);
            // we then merge the sorted sub arrays using the merge method
            Merge(numbers, left, (mid + 1), right, numbers.Length);
        }
    }
}

FireAlkazar · Accepted Answer · 2015-11-25 22:23:02Z

1

left value is changing during merge and as you have code block

while (left <= lEnd)
{
//...
left++;
}

left will be finally assigned to lEnd + 1(the condition for ending while loop).
Otherwise right is not changing and is the last index of currently manipulated sequence.

answered Nov 25, 2015 at 22:23

FireAlkazar

1,8901 gold badge16 silver badges30 bronze badges

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

1 Comment

JH_Dev Over a year ago

Thanks @FireAlkazar that makes a lot of sense finally understand what is going on

bytecode77 · Accepted Answer · 2015-11-25 22:16:44Z

0

Taking the risk of not answering the question like you want it, I would suggest LINQ. This is not merge sort in particular, but rather a concatenation of two arrays and then sorting.

If your array isn't so big that performance matters, you might want to go for this approach, because it's simple and less code (which is always good).

int[] arr1 = new[] { 1, 2, 3, 7, 8, 10 };
int[] arr2 = new[] { 4, 6, 9, 12, 15 };

int[] merged = arr1.Concat(arr2).OrderBy(n => n).ToArray();

Furthermore, I post this if it is interesting for others.

answered Nov 25, 2015 at 22:16

bytecode77

15k31 gold badges119 silver badges151 bronze badges

Collectives™ on Stack Overflow

merge sort implementation query

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related