mergesort.cs

static void msort(int[] arr)
        {
            if (arr.Length == 1)
                return;
            
            //get a half point
            int mid = arr.Length/2;
            int[] left = new int[mid];
            int[] right = new int[arr.Length - mid]; //reason for length - mid is due to halfpoint of an odd length array

            //fill up left - to the half point from original
            for (int i = 0; i < mid; i++)
            {
                left[i] = arr[i];
            }

            //fill up right - need j because right arr starts at 0, start at mid for the parent array
            for (int i = mid, j = 0; i < arr.Length; i++, j++)
            {
                right[j] = arr[i];
            }

            //you have 2 arrays, so sort both of them
            //you can of course use merge to return a new array
            //but its better to sort the array in space
            msort(left);
            msort(right);

            //each sort has to merge the 2 halves, this is techincally where the "sort" happens
            //the 2 halves starting with the most smallest arrays of 1 item
            //this will sort those 2 arrays items and put them into the parent array
            merge(left, right, arr );
        }

        private static void merge(int[] arrA, int[] arrB, int[] aux)
        {
            //you can of course return a "new" array here, but why allocate more
            int aindex = 0;
            int bindex = 0;
            int auxindex = 0;
            //we need to compare each element in both arrays and only pick the smallest one
            //once the smallest one is picked, increment in indexer in the array it was picked from
            //and leave the other indexer untouched.
            //always increment the auxilary index
            while (aindex < arrA.Length && bindex < arrB.Length)
            {
                if (arrA[aindex] < arrB[bindex])
                {
                    aux[auxindex] = arrA[aindex];
                    aindex++;
                }
                else if (arrB[bindex] < arrA[aindex])
                {
                    aux[auxindex] = arrB[bindex];
                    bindex++;
                }
                else
                {
                    //numbers are identical, makes no difference, just pick from one array and increment it
                    aux[auxindex] = arrA[aindex];
                    aindex++;
                }

                auxindex++;
            }

            //in the even that all the smallest numbers were in one of the arrays instead of other
            //we need to fill up the parent array with the items from the other side, so just
            //fill up until we cant anymore
            //first do from A Array
            while (aindex < arrA.Length)
            {
                aux[auxindex] = arrA[aindex];
                aindex++;
                auxindex++;
            }
            //then do the same from B array
            while (bindex < arrB.Length)
            {
                aux[auxindex] = arrB[bindex];
                bindex++;
                auxindex++;
            }

            //done :D
    }