<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body text="#000000" bgcolor="#ffffff">
    On 04/06/2011 03:18 AM, Marek Safar wrote:
    <blockquote cite="mid:4D9C13DE.7050008@gmail.com" type="cite">
      <meta content="text/html; charset=ISO-8859-1"
        http-equiv="Content-Type">
      <title></title>
      Hello,<br>
      <br>
      &gt;&gt;&gt;<br>
      <pre wrap="">        public class Sort&lt;T&gt; {
                public delegate int Comparison (T v0, T v1);

You don't need yet another delegate, just use standard Func

&gt;&gt;
                static readonly int INSERTIONSORT_THRESHOLD = 7;

Why not to used const int ?
</pre>
      <br>
      More importantly what is performance of sorting array of 10-20
      elements called 1000000 times ?<br>
      <br>
    </blockquote>
    <br>
    Attached is another test program with 2 newer/faster implementations
    of QuickSort, one of which is Non-Recursive.<br>
    <br>
    You can run this program like so:<br>
    <br>
    mono ./qsort.exe [-random, -sorted, -reversed] [array size] [#
    loops]<br>
    <br>
    These 2 new implementations manage to reduce the number of
    comparisons done by merging the Median() function from the previous
    set into the main body of the QuickSort function and swapping those
    3 elements into ascending order as it compares to find the optimal
    pivot. This has the advantage of allowing our loops to start at
    low+1 and high-1 (thus reducing our compares by 2 for each
    partition).<br>
    <br>
    My previous implementation was able to reduce the compares by 1 by
    starting at low+1 by moving the pivot into low, but this has the
    negative impact of destroying performance on reverse-sorted arrays.
    My new implementation doesn't have this problem (and therefore, we
    don't need to fall back to that insertion-sort if we detect that
    pathological case).<br>
    <br>
    Interestingly, the NonRecursiveQuickSort() implementation does not
    noticeably improve performance over the recursive version and in
    fact is slower than even our current implementation for sorting
    small arrays (made evident when looped millions of times).<br>
    <br>
    How do you feel about replacing corlib's qsort() implementation with
    my FasterQuickSort() implementation?<br>
    <br>
    Jeff<br>
    <br>
  </body>
</html>