From a day to a few minutes: sorting and binary search

Created: April 10, 2001 Updated: Sept. 29, 2026

Respondent selection ran all night and part of the next day, and two algorithms from university were enough to fix it.

When I joined, Pascal ruled, along with the scripts for selecting research samples. The scripts were built on Pascal collections and searched linearly, so whenever something had to be found in something else, every element meant walking through the whole other list, O(n²).

With small samples nobody noticed, with large ones my boss would come to work in the morning carrying his laptop like a pizza box, because respondent selection was still running from the day before.

I had just studied algorithms and knew two things that fitted perfectly here: sorting and binary search. I sort the list once, and then instead of walking through it from the start every time, I search it by halving, so every lookup takes log n comparisons instead of n.

pascal
{ before: the whole list from the start for every respondent }
for i := 1 to RespCount do
  for j := 1 to UsedCount do
    if Resp[i].Id = Used[j] then
      Skip(i);

{ after: sort once, then binary search }
SortIds(Used, UsedCount);
for i := 1 to RespCount do
  if BinarySearch(Used, UsedCount, Resp[i].Id) then
    Skip(i);

Something that took a day now takes a few minutes, my boss stopped carrying his laptop like a pizza, and I earned his respect.

#pascal #algorytmy #wydajnosc

Machine-translated from Polish (original).