Fastest and Almost Forgotten: Martin Rem's Union-Find in Go

bugfix-66 · on Oct 4, 2022

This algorithm (by far the fastest union-find algorithm, in practice) was almost forgotten.

Eventually found in 2010 by Mostofa Ali Patwary et al., Rem's algorithm was buried in Chapter 23 of Dijkstra's book "A Discipline of Programming":

We present a simplified and more efficient variation on the algorithm. To fix the bug, replace the second

  return i1

with

  return i2

in the Find method.

metadat · on Oct 4, 2022

I love this! Clever idea.

Thank you bugfix-66!