QuickSortAlgorithm

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QuickSortAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            //Task 14: Write a program that sorts an array of strings using
            //the quick sort algorithm (find it in Wikipedia).

            Console.WriteLine("Please enter number of elements: ");
            int numElements = int.Parse(Console.ReadLine());

            string[] elements = new string[numElements];

            // Input elements
            for (int i = 0; i < numElements; i++)
            {
                Console.WriteLine("Please enter element {0}: ", i);
                elements[i] = Console.ReadLine();
            }

            // Quick Sort
            bool[] elementIsPivot = new bool[numElements];    // Here we will put markers for pivots; 'true' means we have pivot in the same place of elements[]
            while (true)    // Condition TBD
            {
                int startIndex = 0;
                int endIndex = numElements - 1;

                int index = 0;
                bool subIntervalFound = false;

                while (index < numElements) // Until reach the end of elements[]
                {
                    // search for false in pivotMarks[]
                    while (elementIsPivot[index])
                    {
                        index++;
                        if (index == numElements)
                        {
                            break;
                        }
                    }

                    // we have found the start of current subinterval
                    startIndex = index;
                    if (startIndex == numElements)
                    {
                        // We have finished the current pass
                        break;
                    }

                    // search for true ahead - to determine the end index of current subinterval
                    while (!elementIsPivot[index])
                    {
                        subIntervalFound = true;
                        index++;
                        if (index == numElements)
                        {
                            break;
                        }
                    }

                    // we have found the end of current subinterval
                    endIndex = index - 1;

                    // We have found the next subinterval, process it!
                    int subLength = endIndex - startIndex + 1;
                    string[] subInterval = new string[subLength];
                    int pivotIndex = (endIndex + startIndex + 1) / 2;

                    int newSubIndex = 0;

                    // First, copy all elements smaller than pivot in the beginning of subinterval
                    for (int subIndex = 0; subIndex < subLength; subIndex++)
                    {
                        //if (elements[startIndex + subIndex] < elements[pivotIndex])
                        if (elements[startIndex + subIndex].CompareTo(elements[pivotIndex]) < 0)
                        {
                            subInterval[newSubIndex] = elements[startIndex + subIndex];
                            newSubIndex++;
                        }
                    }

                    // Mark the new (permanent) place of the current pivot! (Put Circle!) and copy the pivot itself
                    subInterval[newSubIndex] = elements[pivotIndex];
                    elementIsPivot[newSubIndex + startIndex] = true;

                    newSubIndex++;

                    // Then, copy all elements greater than or equal to the pivot, after it
                    for (int subIndex = 0; subIndex < subLength; subIndex++)
                    {
                        //if (elements[startIndex + subIndex] >= elements[pivotIndex] && (startIndex + subIndex != pivotIndex))
                        if (elements[startIndex + subIndex].CompareTo(elements[pivotIndex]) >= 0 && (startIndex + subIndex != pivotIndex))
                        {
                            subInterval[newSubIndex] = elements[startIndex + subIndex];
                            newSubIndex++;
                        }
                    }

                    // Copy the processed elements back to the original elements[] array
                    for (int subIndex = 0; subIndex < subLength; subIndex++)
                    {
                        elements[subIndex + startIndex] = subInterval[subIndex];
                    }
                }

                if (!subIntervalFound)
                {
                    break;
                }
            }

            // Output elements
            for (int i = 0; i < numElements; i++)
            {
                Console.WriteLine("element {0}: {1}", i, elements[i]);
            }
        }
    }
}