Write a program to demonstrate stooge sort algorithm.

Solution:

using System;

namespace StoogeSort
{
    class Program
    {
        static void Main()
        {
            int[] arr = { 89, 2, 12, 44, 90, 88, 46 };
            var n = arr.Length;

            Console.WriteLine("Array before sorting");
            for (var i = 0; i < n; i++)
                Console.WriteLine(arr[i]);

            Sort(arr, 0, n - 1);

            Console.WriteLine("Array after sorting");
            for (var i = 0; i < n; i++)
                Console.WriteLine(arr[i]);

            Console.ReadLine();
        }

        static void Sort(int[] arr, int startPos, int length)
        {
            if (startPos >= length)
                return;

            if (arr[startPos] > arr[length])
            {
                var temp = arr[startPos];
                arr[startPos] = arr[length];
                arr[length] = temp;
            }

            if (length - startPos + 1 <= 2) return;

            var pos = (length - startPos + 1) / 3;

            Sort(arr, startPos, length - pos);
            Sort(arr, startPos + pos, length);
            Sort(arr, startPos, length - pos);
        }
    }
}