quicksort experiments

quicksort.cs

using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication11 {
    class Program {
        private static void SpeedBoost() {
#if !DEBUG
            Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
            Thread.CurrentThread.Priority = ThreadPriority.Highest;
#endif
        }
        static int[] initial; //generating random array only once and using copies of it later
        static void Main2(string[] args) {
            var abc = new[] {1, 2, 3};
            foreach (var s in abc.SelectMany(a=>abc.SelectMany(b=>abc.Select(c=>new[]{a,b,c})))) {
                int[] temp = new[] {s[0], s[1], s[2]};
                ChoosePivot(ref temp, 0, 3);
                Console.WriteLine("{0}{1}{2} {3}{4}{5}",s[0], s[1], s[2],temp[0],temp[1],temp[2]);
            }
            Console.ReadKey();
        }

// ReSharper disable InconsistentNaming
        private static int ChoosePivot(ref int[] _elements, int low, int high) {
// ReSharper restore InconsistentNaming
            high--;
            var mid = (low + high) >> 1;
            var pivot = _elements[high];
            var pivot2 = _elements[low];
            var pivot3 = _elements[mid];

            var hightolow = pivot.CompareTo(pivot2);
            if (hightolow == 0) {
                return pivot;
            }
            var hightomid = pivot.CompareTo(pivot3);
            if (hightolow < 0) {
                if (hightomid < 0) {
                    if (pivot2.CompareTo(pivot3) < 0) {
                        _elements[high] = pivot2;
                        _elements[low] = pivot;
                        pivot = pivot2;
                    } else {
                        _elements[high] = pivot3;
                        _elements[mid] = pivot;
                        pivot = pivot3;
                    }
                }
            } else if (hightomid > 0) {
                if (pivot2.CompareTo(pivot3) < 0) {
                    _elements[high] = pivot3;
                    _elements[mid] = pivot;
                    pivot = pivot3;
                } else {
                    _elements[high] = pivot2;
                    _elements[low] = pivot;
                    pivot = pivot2;
                }
            }
            return pivot;
        }

        private static void Main(string[] args) {
            SpeedBoost();
            initial = Enumerable.Range(0, 100000000).ToArray();
            Shuffle();
            TestLength<Quicksort<int>>(5);
            TestLength<Quicksort<int>>(10);
            TestLength<Quicksort<int>>(100);
            TestLength<Quicksort<int>>(1000);
            TestLength<Quicksort<int>>(10000);
            TestLength<Quicksort<int>>(100000);
            TestLength<Quicksort<int>>(1000000);
            TestLength<Quicksort<int>>(10000000);

            TestLength<Quicksort<int>>(100000000);
            Console.ReadKey();
        }

        private static void Shuffle() {
            //simple Fisher-Yates shuffle
            var random = new Random();
            for (int i = initial.Length - 1; i > 0; i--) {
                int j = random.Next(i);
                int value = initial[i];
                initial[i] = initial[j];
                initial[j] = value;
            }
        }

        private static void TestLength<T>(int length) where T : ISortAlgorithm<int>, new() {
            var arr = new int[length];

            Console.WriteLine("Length: " + length);

            Array.Copy(initial, arr, length);
            var timer = new Stopwatch();
            var algorithm = new T { Elements = arr };
            timer.Start();
            algorithm.ParallelSort();
            timer.Stop();
            Console.WriteLine("Elapsed para: " + timer.Elapsed);

            Array.Copy(initial, arr, length);
            timer.Reset();
            algorithm = new T { Elements = arr };
            timer.Start();
            algorithm.Sort();
            timer.Stop();
            Console.WriteLine("Elapsed:      " + timer.Elapsed);
            
            Array.Copy(initial, arr, length);
            timer.Reset();
            timer.Start();
            QS.Sort(arr);
            timer.Stop();
            Console.WriteLine("Elapsed stat: " + timer.Elapsed);

            Array.Copy(initial, arr, length);
            timer.Reset();
            timer.Start();
            Array.Sort(arr);
            timer.Stop();
            Console.WriteLine("Elapsed stat: " + timer.Elapsed);
            Console.WriteLine();
        }
    }

    public interface ISortAlgorithm<T> where T : IComparable {
        T[] Elements { get; set; }
        void ParallelSort();
        void Sort();
        void SortNoRecursion();
    }

    public static class QS {
        public static void Sort<T>(T[] elements) where T:IComparable<T> {
            var threshold = Math.Max(5, (int)Math.Sqrt(Math.Log(elements.Length)));
            Sort(elements, threshold, 0, elements.Length, 0, (int)Math.Log(Environment.ProcessorCount, 2) + 4);
            InsertSort(elements);
        }
        static void InsertSort<T>(T[] elements) where T : IComparable<T> {
            var length = elements.Length;
            for (var i = 1; i < length; i++) {
                var x = elements[i];
                var j = i;
                while (j > 0 && x.CompareTo(elements[j - 1]) < 0) {
                    elements[j] = elements[j - 1];
                    j--;
                }
                elements[j] = x;
            }
        }

        static void Sort<T>(T[] elements, int threshold, int low, int high, int depth, int pdepth) where T : IComparable<T> {
            if (high - low < threshold) {
                return;
            }
            if (depth > 7000) {
                //avoids stack overflow
                SortNoRecursion(elements, threshold, low, high);
                return;
            }

            var mid = Partition(elements, low, high);

            if (pdepth > 0) {
                Parallel.Invoke(
                    () => Sort(elements, threshold, low, mid, depth + 1, pdepth - 1),
                    () => Sort(elements, threshold, mid + 1, high, depth + 1, pdepth - 1)
                    );
            } else {
                Sort(elements, threshold, low, mid, depth + 1, 0);
                Sort(elements, threshold, mid + 1, high, depth + 1, 0);
            }
        }

        private struct Frame {
            public int Low;
            public int High;
        }

        private static void SortNoRecursion<T>(T[] elements, int threshold, int low, int high) where T : IComparable<T> {
            var stack = new Stack<Frame>();
            stack.Push(new Frame { Low = low, High = high });
            while (stack.Count > 0) {
                var frame = stack.Pop();
                low = frame.Low;
                high = frame.High;

                if (high - low < threshold) {
                    continue;
                }

                var mid = Partition(elements, low, high);

                stack.Push(new Frame { Low = low, High = mid });
                stack.Push(new Frame { Low = mid + 1, High = high });
            }
        }

        static int Partition<T>(T[] elements, int low, int high) where T : IComparable<T> {
            high--;
            var pivot = ChoosePivot(elements, low, high);
            var store = low;
            for (var i = low; i < high; i++) {
                if (elements[i].CompareTo(pivot)>= 0) {
                    continue;
                }
                var temp = elements[store];
                elements[store] = elements[i];
                elements[i] = temp;
                store++;
            }
            elements[high] = elements[store];
            elements[store] = pivot;
            return store;
        }

        private static T ChoosePivot<T>(T[] elements, int low, int high) where T : IComparable<T> {
            var mid = (low + high) >> 1;
            var pivot = elements[high];
            var pivot2 = elements[low];
            var pivot3 = elements[mid];

            var hightolow = pivot.CompareTo(pivot2);
            if (hightolow == 0) {
                return pivot;
            }
            var hightomid = pivot .CompareTo( pivot3);
            if (hightomid == 0) {
                return pivot;
            }
            var lowtomid = pivot2 .CompareTo(pivot3);
            if (lowtomid == 0) {
                return pivot;
            }
            if (hightolow < 0) {
                if (hightomid < 0) {
                    if (lowtomid < 0) {
                        elements[high] = pivot2;
                        elements[low] = pivot;
                        pivot = pivot2;
                    } else {
                        elements[high] = pivot3;
                        elements[mid] = pivot;
                        pivot = pivot3;
                    }
                }
            } else if (hightomid > 0) {
                if (lowtomid < 0) {
                    elements[high] = pivot3;
                    elements[mid] = pivot;
                    pivot = pivot3;
                } else {
                    elements[high] = pivot2;
                    elements[low] = pivot;
                    pivot = pivot2;
                }
            }
            return pivot;
        }
    }

    public sealed class Quicksort<T> : ISortAlgorithm<T> where T : IComparable {
        T[] _elements;
        int _threshold;
        
        //begin interface implementation
        public T[] Elements {
            get {
                return _elements;
            }
            set {
                _elements = value;
                _threshold = Math.Max(5,(int)Math.Sqrt(Math.Log(value.Length)));
            }
        }

        public void ParallelSort() {
            Sort(0, _elements.Length, 0, (int)Math.Log(Environment.ProcessorCount, 2)+4 );
            var s = new InsertionSort<T> {
                Elements = _elements
            };
            s.SortNoRecursion();
        }

        public void Sort() {
            Sort(0, _elements.Length, 0, 0);
            var s = new InsertionSort<T> {
                Elements = _elements
            };
            s.SortNoRecursion();
        }

        public void SortNoRecursion() {
            SortNoRecursion(0, _elements.Length);
            var s = new InsertionSort<T> {
                Elements = _elements
            };
            s.SortNoRecursion();
        }
        //end interface implementation

        private void Sort(int low, int high, int depth, int pdepth) {
            if (high - low < _threshold) {
                return;
            }
            if (depth > 7000) {
                //avoids stack overflow
                SortNoRecursion(low, high);
                return;
            }

            var mid = Partition(low, high);

            if (pdepth > 0) {
                Parallel.Invoke(
                    () => Sort(low, mid, depth + 1, pdepth - 1),
                    () => Sort(mid + 1, high, depth + 1, pdepth - 1)
                    );
            } else {
                Sort(low, mid, depth + 1, 0);
                Sort(mid + 1, high, depth + 1, 0);
            }
        }

        private struct Frame {
            public int Low;
            public int High;
        }

        private void SortNoRecursion(int low, int high) {
            var stack = new Stack<Frame>();
            stack.Push(new Frame { Low = low, High = high });
            while (stack.Count > 0) {
                var frame = stack.Pop();
                low = frame.Low;
                high = frame.High;

                if (high - low < _threshold) {
                    continue;
                }

                var mid = Partition(low, high);

                stack.Push(new Frame { Low = low, High = mid });
                stack.Push(new Frame { Low = mid + 1, High = high });
            }
        }

        private int Partition(int low, int high) {
            high--;
            var pivot = ChoosePivot(low, high);
            var store = low;
            for (var i = low; i < high; i++) {
                if (_elements[i].CompareTo(pivot) >= 0) {
                    continue;
                }
                var temp = _elements[store];
                _elements[store] = _elements[i];
                _elements[i] = temp;
                store++;
            }
            _elements[high] = _elements[store];
            _elements[store] = pivot;
            return store;
        }

        private T ChoosePivot(int low, int high) {
            var mid = (low + high) >> 1;
            var pivot = _elements[high];
            var pivot2 = _elements[low];
            var pivot3 = _elements[mid];

            var hightolow = pivot.CompareTo(pivot2);
            if (hightolow == 0) {
                return pivot;
            }
            var hightomid = pivot.CompareTo(pivot3);
            if (hightomid == 0) {
                return pivot;
            }
            var lowtomid = pivot2.CompareTo(pivot3);
            if (lowtomid == 0) {
                return pivot;
            }
            if (hightolow < 0) {
                if (hightomid < 0) {
                    if (lowtomid < 0) {
                        _elements[high] = pivot2;
                        _elements[low] = pivot;
                        pivot = pivot2;
                    } else {
                        _elements[high] = pivot3;
                        _elements[mid] = pivot;
                        pivot = pivot3;
                    }
                }
            } else if (hightomid > 0) {
                if (lowtomid < 0) {
                    _elements[high] = pivot3;
                    _elements[mid] = pivot;
                    pivot = pivot3;
                } else {
                    _elements[high] = pivot2;
                    _elements[low] = pivot;
                    pivot = pivot2;
                }
            }
            return pivot;
        }
//        T ChoosePivot(int low, int high) {
//            high--;
//            var mid = (low + high) >> 1;
//
//            if (_elements[mid].CompareTo(_elements[low]) < 0) {
//                var temp = _elements[low];
//                _elements[low] = _elements[mid];
//                _elements[mid] = temp;
//            }
//            if (_elements[high].CompareTo(_elements[mid]) < 0) {
//                if (_elements[high].CompareTo(_elements[low]) > 0) {
//                    return _elements[high];
//                }
//                var temp = _elements[mid];
//                _elements[mid] = _elements[high];
//                _elements[high] = temp;
//            }
//            return _elements[high];
//        }
    }

    public sealed class InsertionSort<T> : ISortAlgorithm<T> where T : IComparable {
        T[] _elements;
        public T[] Elements { get { return _elements; } set { _elements = value; } }
        public void ParallelSort() {
            SortNoRecursion();
        }
        public void Sort() {
            SortNoRecursion();
        }
        public void SortNoRecursion() {
            var length = _elements.Length;
            for (var i = 1; i < length; i++) {
                var x = _elements[i];
                var j = i;
                while (j > 0 && x.CompareTo(_elements[j - 1]) < 0) {
                    _elements[j] = _elements[j - 1];
                    j--;
                }
                _elements[j] = x;
            }
        }
    }
}