Fixed a variety of multi-threading data races, detected through
1000 repeated runs of the same command at approximately the 2% failure
level on unsorted data only.

clang -fsanitize=thread has been instrumental in identifying the
causes. It gets my recommendation.