<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
    <title></title>
  </head>
  <body text="#000000" bgcolor="#ffffff">
    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>
    Thanks<br>
    Marek<br>
    <br>
    <blockquote cite="mid:4D9B9C5B.9050709@novell.com" type="cite">Attached
      you'll find qsort.cs which includes 3 QuickSort implementations:
      <br>
      <br>
      1. QuickSortBasic[R]: This is a basic QuickSort implementation and
      the one currently in use as the sorting function in Array.Sort().
      This implementation always uses the middle element as the pivot.
      <br>
      <br>
      2. QuickSortMedian[R]: This implementation is also a basic
      QuickSort implementation which attempts choose a better pivot
      based on the first, last, and middle elements. For sorted inputs
      and random inputs, this seems to help performance somewhat as the
      array gets larger and larger. However, for reverse-sorted inputs,
      it seems to kill performance. Perhaps if I choose 3 random points
      to feed into Median() it will do better.
      <br>
      <br>
      3. QuickSortInsertion[R]: This implementation includes the above
      perf trick and also includes an Insertion Sort fallback when
      partitions are broken down smaller than some threshold # of
      elements (7 in the attached code). It also falls back to Insertion
      Sort when it encounters a worst-case scenario. As always, the
      performance improvement with this is greater as the number of
      elements increases and/or as the comparison function becomes more
      complex.
      <br>
      <br>
      <br>
      You'll notice that the attached test program will print out the
      number of comparisons that each sort routine uses in order to
      complete its job. It's important to keep in mind that the more
      complex the comparison function is, the more important it is that
      the number of comparisons is kept to a minimum.
      <br>
      <br>
      Here are some example runs:
      <br>
      <br>
      <br>
      [fejj@warpig sorting]$ mono ./qsort.exe -random 100000000
      <br>
      Basic QuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 3807986012
      <br>
      QuickSort+Median comparisons needed:&nbsp;&nbsp;&nbsp; 3077915654
      <br>
      QuickSort+Insertion comparisons needed: 3021355043
      <br>
      Basic QuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp; 00:00:43.8178721s
      <br>
      QuickSort+Median finished in:&nbsp;&nbsp;&nbsp; 00:00:37.3047443s
      <br>
      QuickSort+Insertion finished in: 00:00:36.6122681s
      <br>
      <br>
      <br>
      [fejj@warpig sorting]$ mono ./qsort.exe -sorted 100000000
      <br>
      Basic QuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 2632227866
      <br>
      QuickSort+Median comparisons needed:&nbsp;&nbsp;&nbsp; 2632227867
      <br>
      QuickSort+Insertion comparisons needed: 2483222808
      <br>
      Basic QuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp; 00:00:21.8213618s
      <br>
      QuickSort+Median finished in:&nbsp;&nbsp;&nbsp; 00:00:21.2622527s
      <br>
      QuickSort+Insertion finished in: 00:00:19.0837352s
      <br>
      <br>
      <br>
      (Note: I reduced the array size here due to wanting to head home
      for dinner)
      <br>
      [fejj@warpig sorting]$ mono ./qsort.exe -reversed 10000
      <br>
      Basic QuickSort comparisons needed:&nbsp;&nbsp;&nbsp;&nbsp; 129546
      <br>
      QuickSort+Median comparisons needed:&nbsp;&nbsp;&nbsp; 12522499
      <br>
      QuickSort+Insertion comparisons needed: 39993
      <br>
      Basic QuickSort finished in:&nbsp;&nbsp;&nbsp;&nbsp; 00:00:00.0016905s
      <br>
      QuickSort+Median finished in:&nbsp;&nbsp;&nbsp; 00:00:00.0911385s
      <br>
      QuickSort+Insertion finished in: 00:00:00.0008721s
      <br>
      <br>
      <br>
      Jeff
      <br>
      <pre wrap="">
<fieldset class="mimeAttachmentHeader"></fieldset>
_______________________________________________
Mono-devel-list mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Mono-devel-list@lists.ximian.com">Mono-devel-list@lists.ximian.com</a>
<a class="moz-txt-link-freetext" href="http://lists.ximian.com/mailman/listinfo/mono-devel-list">http://lists.ximian.com/mailman/listinfo/mono-devel-list</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>