A 315 student sent me a report on his experiments with Quick Sort:<P>

"Here are the preliminary results (program written in C++ (With
templates(TM)), using Microsofts VC 5.0):"

<ul>

<li> Using an  array of increasing values:<P>


<table border=2>
<tr><td>input size</td><td>time [ms.]</td></tr>

<tr><td>1,000</td><td> 1</td></tr>

<tr><td>10,000</td><td>4</td></tr>

<tr><td>100,000</td><td>64</td></tr><tr>

<tr><td>1,000,000</td><td>594</td></tr></table>

<P><li> Using an array of the same values:<P>

<table border=2>
<tr><td>input size</td><td>time [ms.]</td></tr>

<tr><td>1,000</td><td> 1</td></tr>

<tr><td>10,000</td><td>6</td></tr>

<tr><td>100,000</td><td>80</td></tr><tr>

<tr><td>1,000,000</td><td>946</td></tr></table>

<P><li> Using an array of  random values:<P>

<table border=2>
<tr><td>input size</td><td>time [ms.]</td></tr>

<tr><td>1,000</td><td> 1</td></tr>

<tr><td>10,000</td><td>10</td></tr>

<tr><td>100,000</td><td>71</td></tr><tr>

<tr><td>1,000,000</td><td>1487</td></tr></table>

<P></ul><P>

This experiment have brought some questions: what implementation was
used? what do the different constants (interpolating T(n)=cnlogn) for
each set of data tell us? how relevant is the factor 2 with which we
came up in the analysis of expected complexity?<p>

At the moment, we are just asking... The answers will be due soon.