I managed to solve it using the Barrier class. Many thanks to Damien_The_Unbeliever! Still can't believe I haven't heard of it before.
public Barrier barrier = new barrier(1);
public void RunAlgorithm(List<City> cities){
List<Thread> localThreads = new List<Thread>();
object[] temp = //some parameters here
for(int i = 0; i < numOfCitiesToCheck; i++){
barrier.AddParticipant();
Thread newThread = new Thread((o) => DoWork(o as object[]));
newThread.IsBackground = true;
newThread.Priority = ThreadPriority.AboveNormal;
newThread.Start(temp as object);
localThreads.Add(newThread);
}
barrier.SignalAndWait();
int counter = 0;
while(true){
if(counter == localThreads.Count){ break; }
localThreads[counter].Join();
counter++;
}
}
private void DoWork(object[] arguments){
barrier.SignalAndWait();
GoDoWork(arguments);
}