<!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/09/2011 04:39 PM, Jeff Stedfast wrote:
    <blockquote cite="mid:4DA0C40F.3050000@novell.com" type="cite">
      <meta content="text/html; charset=ISO-8859-1"
        http-equiv="Content-Type">
      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>
    </blockquote>
    <br>
    Just to be clear, I meant "how do you feel about *me* doing the work
    to replace the current QuickSort impl in corlib with mine?" :-)<br>
    <br>
    I just want to make sure before I create a patch that people are
    interested.<br>
    <br>
    That said, I forgot to include benchmark results:<br>
    <br>
    [fejj@serenity sorting]$ mono ./qsort.exe -random 10 10000000<br>
    BasicQuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 430000000<br>
    FasterQuickSort comparisons needed:&nbsp;&nbsp;&nbsp; 250000000<br>
    BasicQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:18.8535031s<br>
    FasterQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:16.4478594s<br>
    <br>
    [fejj@serenity sorting]$ mono ./qsort.exe -sorted 10 10000000<br>
    BasicQuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 330000000<br>
    FasterQuickSort comparisons needed:&nbsp;&nbsp;&nbsp; 180000000<br>
    BasicQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:16.9532771s<br>
    FasterQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:14.1202212s<br>
    <br>
    [fejj@serenity sorting]$ mono ./qsort.exe -reversed 10 10000000<br>
    BasicQuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 360000000<br>
    FasterQuickSort comparisons needed:&nbsp;&nbsp;&nbsp; 180000000<br>
    BasicQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:17.4450895s<br>
    FasterQuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00:00:15.1590930s<br>
    <br>
    <br>
    Jeff<br>
    <br>
  </body>
</html>