High-Volume Test of a Sort Routine

The zip file below contains a small C# program that performs high-volume testing of a sorting routine called "ShearSort".

The test program works as follows:

  1. Generate an ordered list;

  2. Shuffle the list;

  3. Send the shuffled list to the ShearSort routine;

  4. Verify that the sorted output is correct;

  5. Repeat.

Steps to run the program:

  1. Download and unzip ShearSortHighVolumeTest.zip.

  2. Open ShearSortHighVolumeTest.cs in an editor.

  3. Create a new C# console project in Visual Studio.

  4. Paste the contents of ShearSortHighVolumeTest.cs over the Program.cs content in Visual Studio.

  5. Save Program.cs.

  6. Build and run the solution.

Test results will show up in a prompt window, of the form:

Sort fail! size=9 input [6, 9, 1, 4, 7, 5, 8, 2, 3] output [1, 2, 4, 3, 6, 7, 5, 8, 9]

Points of interest:

  • The program tests lists from size 2 to size 10.

  • The program tests 500 random shuffles at each list size.

  • You can increase the upper bound of list size by changing the variable largeSetSize.

  • The bug first shows up at list size 9.

  • You can fix the bug by changing the “<” to “<=” in line 90 (see comment in the code)


Harry and Doug

PS: We simplified the pseudo-code listings after our article went to press.