An Analysis of Algorithms for the Dutch National Flag Problem Solutions to the Dutch National Flag Problem have been given by Dijkstra [1] and Meyer [3]. Dijkstra starts with a simple program and arrives at an improved program by refinement. Both of the algorithms given by Dijkstra are shown to have an expected number of swaps which is 2/3N + 0(1) and that these values differ at most by 1/3 of a swap and asymptotically by 1/4 of a swap. The algorithm of Meyer is shown to have expected swap complexity 5/9N. CACM October, 1978 McMaster, C. Algorithmic analysis, Dutch National Flag Problem, refinement, structured programming 4.0 5.24 5.25 5.3 CA781006 DH January 29, 1979 5:47 PM 3055 5 3055 3055 5 3055 3055 5 3055 3170 5 3055 3055 6 3055 3104 6 3055