static void QuickSort(int[] lst, int start, int end)
        {
            if (start >= end)
            {
                return;
            }

            int pivot = Partition(lst, start, end);
            QuickSort(lst, start, pivot - 1);
            QuickSort(lst, pivot + 1, end);
        }

        static int Partition(int[] lst, int start, int end)
        {
            int temp;
            int marker = start;
            for ( int i = start; i <= end; i++ )
            {
                if ( lst[i] < lst[end] )
                {
                    temp = lst[marker];
                    lst[marker] = lst[i];
                    lst[i] = temp;
                    marker += 1;
                }
            }
            temp = lst[marker];
            lst[marker] = lst[end];
            lst[end] = temp;
            return marker;
        }

        static void MergeSort(int[] lst, int begin, int end)
        {
            if (begin < end)
            {
                int half = (begin + end) / 2;
                MergeSort(lst, begin, half);
                MergeSort(lst, half + 1, end);
                Merge(lst, begin, half, end);
            }
        }

        static void Merge(int[] lst, int begin, int half, int end)
        {
            int[] leftArray = new int[half - begin + 1];
            int[] rightArray = new int[end - half];

            Array.Copy(lst, begin, leftArray, 0, half - begin + 1);
            Array.Copy(lst, half + 1, rightArray, 0, end - half);

            int i = 0;
            int j = 0;
            for (int k = begin; k < end + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    lst[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    lst[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    lst[k] = leftArray[i];
                    i++;
                }
                else
                {
                    lst[k] = rightArray[j];
                    j++;
                }
            }
        }