Case Study 1: Benchmarking Sort Algorithms

The Question

Every textbook tells you that merge sort is O(n log n) and selection sort is O(n²). But what does that mean in practice? How much faster is one algorithm than another on real data, on real hardware? This case study answers that question by benchmarking four sorting algorithms on arrays of different sizes.

The Benchmarking Program

We measure wall-clock time and comparison counts for selection sort, insertion sort, merge sort, and quicksort on arrays ranging from 100 to 100,000 elements.

program SortBenchmark;

uses
  SysUtils, DateUtils;

var
  CompCount: Int64;  { Global comparison counter }

{ --- Sorting Algorithms with Counting --- }

procedure SelectionSortCounted(var Arr: array of Integer; N: Integer);
var
  I, J, MinIdx, Temp: Integer;
begin
  for I := 0 to N - 2 do begin
    MinIdx := I;
    for J := I + 1 to N - 1 do begin
      Inc(CompCount);
      if Arr[J] < Arr[MinIdx] then
        MinIdx := J;
    end;
    Temp := Arr[I];
    Arr[I] := Arr[MinIdx];
    Arr[MinIdx] := Temp;
  end;
end;

procedure InsertionSortCounted(var Arr: array of Integer; N: Integer);
var
  I, J, Key: Integer;
begin
  for I := 1 to N - 1 do begin
    Key := Arr[I];
    J := I - 1;
    while J >= 0 do begin
      Inc(CompCount);
      if Arr[J] > Key then begin
        Arr[J + 1] := Arr[J];
        Dec(J);
      end
      else
        Break;
    end;
    Arr[J + 1] := Key;
  end;
end;

procedure MergeCounted(var Arr: array of Integer; L, M, R: Integer);
var
  Temp: array of Integer;
  I, J, K, Size: Integer;
begin
  Size := R - L + 1;
  SetLength(Temp, Size);
  I := L; J := M + 1; K := 0;
  while (I <= M) and (J <= R) do begin
    Inc(CompCount);
    if Arr[I] <= Arr[J] then begin
      Temp[K] := Arr[I]; Inc(I);
    end else begin
      Temp[K] := Arr[J]; Inc(J);
    end;
    Inc(K);
  end;
  while I <= M do begin Temp[K] := Arr[I]; Inc(I); Inc(K); end;
  while J <= R do begin Temp[K] := Arr[J]; Inc(J); Inc(K); end;
  for I := 0 to Size - 1 do
    Arr[L + I] := Temp[I];
end;

procedure MergeSortCounted(var Arr: array of Integer; L, R: Integer);
var
  M: Integer;
begin
  if L >= R then Exit;
  M := (L + R) div 2;
  MergeSortCounted(Arr, L, M);
  MergeSortCounted(Arr, M + 1, R);
  MergeCounted(Arr, L, M, R);
end;

function PartitionCounted(var Arr: array of Integer; Lo, Hi: Integer): Integer;
var
  Pivot, Temp, I, J: Integer;
begin
  Pivot := Arr[Hi];
  I := Lo - 1;
  for J := Lo to Hi - 1 do begin
    Inc(CompCount);
    if Arr[J] <= Pivot then begin
      Inc(I);
      Temp := Arr[I]; Arr[I] := Arr[J]; Arr[J] := Temp;
    end;
  end;
  Temp := Arr[I+1]; Arr[I+1] := Arr[Hi]; Arr[Hi] := Temp;
  PartitionCounted := I + 1;
end;

procedure QuickSortCounted(var Arr: array of Integer; Lo, Hi: Integer);
var
  P: Integer;
begin
  if Lo < Hi then begin
    P := PartitionCounted(Arr, Lo, Hi);
    QuickSortCounted(Arr, Lo, P - 1);
    QuickSortCounted(Arr, P + 1, Hi);
  end;
end;

{ --- Utility --- }

procedure FillRandom(var Arr: array of Integer; N: Integer);
var
  I: Integer;
begin
  for I := 0 to N - 1 do
    Arr[I] := Random(N * 10);
end;

procedure CopyArray(const Src: array of Integer;
                    var Dst: array of Integer; N: Integer);
var
  I: Integer;
begin
  for I := 0 to N - 1 do
    Dst[I] := Src[I];
end;

{ --- Main Benchmark --- }

const
  SIZES: array[1..5] of Integer = (100, 1000, 5000, 10000, 50000);

var
  Master, Work: array of Integer;
  Size, S: Integer;
  StartTime: TDateTime;
  ElapsedMS: Int64;

begin
  Randomize;
  WriteLn('=== Sorting Algorithm Benchmark ===');
  WriteLn;
  WriteLn('Size':8, 'SelSort ms':12, 'comps':14,
          'InsSort ms':12, 'comps':14,
          'Merge ms':12, 'comps':14,
          'Quick ms':12, 'comps':14);
  WriteLn(StringOfChar('-', 120));

  for S := 1 to 5 do begin
    Size := SIZES[S];
    SetLength(Master, Size);
    SetLength(Work, Size);
    FillRandom(Master, Size);

    Write(Size:8);

    { Selection Sort }
    CopyArray(Master, Work, Size);
    CompCount := 0;
    StartTime := Now;
    SelectionSortCounted(Work, Size);
    ElapsedMS := MilliSecondsBetween(Now, StartTime);
    Write(ElapsedMS:12, CompCount:14);

    { Insertion Sort }
    CopyArray(Master, Work, Size);
    CompCount := 0;
    StartTime := Now;
    InsertionSortCounted(Work, Size);
    ElapsedMS := MilliSecondsBetween(Now, StartTime);
    Write(ElapsedMS:12, CompCount:14);

    { Merge Sort }
    CopyArray(Master, Work, Size);
    CompCount := 0;
    StartTime := Now;
    MergeSortCounted(Work, 0, Size - 1);
    ElapsedMS := MilliSecondsBetween(Now, StartTime);
    Write(ElapsedMS:12, CompCount:14);

    { Quicksort }
    CopyArray(Master, Work, Size);
    CompCount := 0;
    StartTime := Now;
    QuickSortCounted(Work, 0, Size - 1);
    ElapsedMS := MilliSecondsBetween(Now, StartTime);
    Write(ElapsedMS:12, CompCount:14);

    WriteLn;
  end;

  WriteLn;
  WriteLn('Benchmark complete.');
end.

Expected Results

On a typical modern machine, you should see results roughly like this:

The O(n²) algorithms become visibly slow around n = 5,000 and painfully slow at n = 50,000. The O(n log n) algorithms remain nearly instantaneous.

Key Observations

1. The n² vs. n log n gap is enormous in practice. At n = 50,000, selection sort takes over 4 seconds while quicksort takes under 10 milliseconds — a 400x speedup.

2. Insertion sort beats selection sort because it is adaptive and can terminate early in the inner loop.

3. Quicksort is typically faster than merge sort despite both being O(n log n), because quicksort has better cache locality and lower constant factors.

4. Comparison counts confirm the theory: Selection sort always makes exactly n(n-1)/2 comparisons. Merge sort and quicksort make approximately n log₂(n) comparisons.

Discussion Questions

1. How would the results change if the input arrays were already sorted? Which algorithms would benefit, and which would suffer?

2. At what array size does it stop making sense to use O(n²) algorithms? Based on your benchmarks, suggest a crossover point.

3. Why does quicksort have better "cache locality" than merge sort? (Hint: think about which memory locations each algorithm accesses.)

4. If you had to sort a million records, how long would selection sort take based on your measurements? Is this acceptable for a user-facing application?