Merge Sort Quick Sort
Implementation

void MeargeSort(int[] arr)
        {
            int[] helper = new int[arr.Length];
            MergeSort(arr, helper, 0, arr.Length);
        }

        void MergeSort(int[] arr, int[] helper, int low, int high)
        {
            if (low < high)
            {
                int middle = (low + high) / 2;
                MergeSort(arr, helper, low, middle);
                MergeSort(arr, helper, low, middle);
                Merge(arr, helper, low, middle, high);
            }
        }

        void Merge(int[] arr, int[] helper, int low, int middle, int high)
        {
            //Copy both halves into a helper array
            for (int i=low; i<=high; i++)
            {
                helper[i] = arr[i];
            }

            int helperLeft = low;
            int helperRight = middle + 1;
            int current = low;
            /*
             Iterate through helper arry. Compare the left and riht half, Copying back
             the smaller element from the two halves into the original array.
             */
            while (helperLeft<= middle && helperRight<= high)
            {
                if (helper[helperLeft]<= helper[helperRight]) {
                    arr[current] = helper[helperLeft];
                    helperLeft++;
                }
                //If right element is small than left element
                else
                {
                    arr[current] = helper[helperRight];
                    helperRight++;
                }
                current++;
            }

            //Copy the rest of the left side of the arry inot the target array
            int remaining = middle - helperLeft;
            for (int i=0; i<= remaining; i++)
            {
                arr[current + i] = helper[helperLeft + i];
            }
        }

void QuickSort(int[] arr, int left, int right)
        {
            int index = QuickSortPartition(arr, left, right);
            //Sort left half
            if (left < index - 1)
            {
                QuickSort(arr, left, index - 1);
            }
            //Sort right half
            if (index < right)
            {
                QuickSort(arr, index, right);
            }

        }

        int QuickSortPartition(int[] arr, int left, int right)
        {
            //Pick Pivote Point
            int pivoteValue = arr[(left + right) / 2];
            while (left <= right)
            {
                //Find element on left that should be on right
                while (arr[left] < pivoteValue) left++;
                //Find element on right that should be on left
                while (arr[left] < pivoteValue) left++;
                //Swap elements, and move left and right indices
                if (left < right)
                {
                    //swaps elements Swap(arr, left, right);
                    arr.Swap(left, right);
                    left++;
                    right--;
                }
            }
            return left;
        }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Time Complexity Worst Case

O(N Log N), where N is the size of the structure (e.g. array).

 

O(N2), where N is the size of the data structure (e.g. array).

The worst case occurs when the array is reverse sorted.

Time Complexity Average Case

O(N Log N), where N is the size of the structure (e.g. array).

 

O(N Log N), where N is the size of the structure (e.g. array).

Works well when the data structure (e.g. array) is randomized.

Space Complexity

Depends.

Merge sort requires O(N) extra storage, where N is the size of the structure (e.g. array).

Constant

 

 

  On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst-case scenarios such as a perfectly sorted array.
Preferred Data structure Linked List Array
Cache Friendly   Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.