· Development

Boyer–Moore majority vote: one candidate, one counter, and why you need a second pass

MJRTY (Boyer and Moore, 1980) picks a majority candidate with one value and one counter. Its rules, why it works, the wrong answer when no majority exists, and the second pass.

algorithmsmajority-votestreamingcomplexity

Say you have n values and want to know whether one of them appears more than half the time, and if so which one. That is finding the winner of a vote by absolute majority, or finding the “majority element” of an array. Majority here means strictly more than n/2. Seven votes out of 13 is a majority; six out of 12 is not.

Robert S. Boyer and J Strother Moore devised an algorithm for this in 1980 that needs only one stored value and one counter. Their paper calls it MJRTY; it is usually known as the Boyer–Moore majority vote algorithm. This post follows the authors’ 1991 paper “MJRTY—A Fast Majority Vote Algorithm” (in the Bledsoe festschrift Automated Reasoning, pp. 105–117, from the PostScript copy the authors host) and the explanation pages Moore published. It leaves out the details of the Fortran verification system in the second half of the paper, and the content of later work that generalises the algorithm.

The obvious approach and its cost

The paper starts with the obvious method: scan the votes once and keep a running tally for each candidate. If the number of candidates is fixed, that runs in time proportional to n. If it is not fixed, storing and retrieving the tallies can make the running time worse than linear in the number of votes, and the paper notes such an algorithm could run in order n².

If the values can be ordered, there is another route. Find the median with a linear-time selection algorithm, then check whether the median received more than half the votes. A majority element, if there is one, always sits in the middle position once the values are sorted (that reason is this post’s explanation). The paper quotes the bound for the Rivest–Tarjan algorithm it would use: at most 5.43n − 163 comparisons when n > 32. Linear-time selection of this kind is covered in Median of medians (BFPRT).

MJRTY needs at most 2n comparisons, and it does not need the values to be ordered at all. In the paper’s words, only comparisons of equality are performed.

Two rules

The algorithm reads the values from front to back, keeping a pair: a current candidate and a counter. At the start the candidate is unknown and the counter is 0. For each element e:

  • If the counter is 0, set the candidate to e and the counter to 1.
  • Otherwise, increment the counter if e equals the current candidate, and decrement it if not.

When every element has been read, the remaining candidate is the majority element, provided there is one. That proviso is the most important part of the algorithm, and it gets its own section below.

The paper explains this with a floor fight at a convention. Every delegate carries a placard naming their candidate, and whenever two delegates for different candidates meet, both knock each other down at the same moment. If one candidate has more delegates than all the others combined, the only people left standing at the end are that candidate’s supporters. Without a majority, someone may still be standing, but there is no guarantee their candidate has a majority. So the chairman has to count the nominee’s placards again, including those held by delegates who were knocked down.

The paper therefore splits the algorithm in two. A “pairing” phase pairs off disagreeing votes, and a “counting” phase checks whether the surviving candidate actually received more than half the votes. According to the paper, pairing can be done with n comparisons, and counting needs at most n comparisons.

Walking through an example

Moore’s page and the paper use the same 13-element sequence:

A A A C C B B C C C B C C

Writing the state after each element as “candidate:counter” gives the same steps as the animation on Moore’s page. A ? means the counter is 0 and there is no candidate.

Step Element State
1 A A:1
2 A A:2
3 A A:3
4 C A:2
5 C A:1
6 B ?:0
7 B B:1
8 C ?:0
9 C C:1
10 C C:2
11 B C:1
12 C C:2
13 C C:3

Following the paper’s commentary: elements 4 to 6 (two Cs and a B) cancel the three A votes and bring the counter to 0. The B at step 7 leads briefly and is cancelled by the C at step 8. After that C pulls ahead and the run ends at C:3. In this sequence C appears 7 times out of 13 (a count done for this post), so it really is the majority.

Note that the final counter, 3, is not C’s vote total. It is the number of C votes left over after pairing.

Why it works

The paper’s proof rests on an invariant. After processing the i-th element, the elements seen so far can be split into two groups:

  • k votes for the candidate cand, where k is the current counter;
  • the rest, which can be paired off so that the two votes in each pair disagree.

If this holds at the end, the conclusion follows. Suppose some x different from cand has more than n/2 votes. Because the second group can be paired into disagreeing pairs, x gets at most (n − k)/2 votes from it. To exceed n/2, x must then also have a vote in the first group, but every vote in the first group is for cand. That is a contradiction, so if there is a majority element, it is cand.

The invariant itself is shown by induction on i. The paper’s cases, summarised:

  • When the counter is 0 and a new element arrives, all elements so far are in the paired group, so the new element alone forms a fresh first group.
  • When the new element equals cand, it joins the first group.
  • When it differs from cand, take one delegate out of the first group, pair it with the new element, and move both to the second group.

Without a majority, you get a wrong answer

The algorithm returns a candidate even when there is no majority. Moore’s example page suggests replacing the first C in the sequence above with an A:

A A A A C B B C C C B C C

Run through the same rules, this still ends at C:3. But now C appears 6 times out of 13, A 4 times and B 3 times (counted for this post). There is no majority element, yet the candidate is C.

The paper has a shorter example too. In A A A B B B C, the As and Bs cancel each other and the final C becomes the candidate “by default”, ending at C:1. The paper adds that had the delegates been polled in a different order, A or B might have won. Without a majority, the candidate that remains depends on the input order and means nothing by itself.

When you can skip the second pass

If you must confirm that the candidate really is the majority, you need one more linear pass over the data to count it. Moore’s page says this plainly. You can drop that pass only when you know, or can assume, that a majority exists.

The paper’s example is the SIFT aircraft control system, which gets its reliability from redundant processors and software voting. There, the failure rate of individual processors is low enough to assume that on a given flight a majority of the working processors agree on each vote. When a majority can be assumed, the counting phase can be removed, and the paper notes the algorithm can then poll the delegates in real time instead of storing the votes for batch processing.

The paper’s Fortran implementation also has a small improvement:

  • If the counter is 0 when pairing ends, it reports that there is no majority straight away.
  • If the counter k is greater than n/2, it announces cand as the majority without the counting phase, because there are at least k votes for cand.

The paper says the same test could be made every time the counter is incremented in the first loop, which would sometimes avoid the second pass; whether that improves running time depends on the distribution of the votes. It also says the authors failed to find a variation of the first phase that makes the second phase unnecessary.

A Python version

The code below is this post’s translation, written to follow the same steps as the paper’s Fortran subroutine. Just as the Fortran version reports its result through two values, BOOLE and CAND, this returns whether a majority exists along with the candidate. It uses a separate flag rather than signalling “no majority” with None, because None could itself be one of the input values.

def majority(xs):
    """Return (whether a majority element exists, that element). Reads xs twice."""
    n = len(xs)
    cand, k = None, 0
    # pairing phase
    for x in xs:
        if k == 0:
            cand, k = x, 1
        elif x == cand:
            k += 1
        else:
            k -= 1
    if k == 0:
        return False, None
    if k > n // 2:
        return True, cand
    # counting phase: check that the candidate really has more than half
    count = 0
    for x in xs:
        if x == cand:
            count += 1
            if count > n // 2:
                return True, cand
    return False, None


print(majority(list("AAACCBBCCCBCC")))  # (True, 'C')
print(majority(list("AAAACBBCCCBCC")))  # (False, None)
print(majority(list("AAABBBC")))        # (False, None)

For integers, count > n // 2 is the same condition as “greater than n/2”. With n = 13, n // 2 is 6, so a count of 7 or more passes. Stopping the counting phase as soon as the count exceeds n/2 also matches the paper’s Fortran code.

A few notes, all of them this post’s own comments on the code:

  • It reads the data twice and calls len(xs) at the start. So this function needs a collection with a known length that can be iterated more than once, such as a list. A one-shot iterator or stream fails at len() right away, even when a majority is guaranteed.
  • It only uses ==. That means it works on values that cannot be sorted or hashed. In exchange, == has to behave consistently. If comparing the same two values can give different results, or a value can compare unequal to itself, the proof’s premise that equal votes form a group no longer holds.
  • Apart from the input, it uses O(1) auxiliary space: the candidate, the counter, n, count and the loop variable, a fixed number of variables whatever the input size.

Cost and access pattern

From the paper:

  • Comparisons: n for pairing and at most n for counting, so at most 2n in total. That is a bound for every input, not a probabilistic or average figure.
  • Kind of comparison: equality only. The values need no order.
  • Access order: it reads the array elements in linear order. The paper points out that this makes it efficient even when there are so many votes that they must be read from magnetic tape; one tape rewind may be needed after the first phase.

How it got published

The “Postscript 1991” section at the end of the paper tells the publication story. The algorithm was invented in 1980 while both authors were at SRI International. A colleague working on fault tolerance, who was trying to specify algorithms in the logic of the Boyer–Moore theorem prover, asked them for an elegant definition of the majority element of a list within that logic; their answer was the recursive expression of this algorithm. In late 1980 they wrote a Fortran version and proved it correct mechanically, and in February 1981 they wrote the paper and submitted it.

In 1981 they moved to the University of Texas. According to a private communication from Jay Misra (1990) quoted in the paper, Misra heard their presentation and wondered how to generalise it to detect elements occurring more than n/k times; with David Gries he later published “Finding Repeated Elements” (Science of Computer Programming 2, 1982), which cited Boyer and Moore’s technical report as “submitted for publication”.

Boyer and Moore’s own paper, meanwhile, was repeatedly rejected, largely because of its emphasis on Fortran and mechanical verification. A rewritten version focusing on the algorithm was rejected on the grounds that the work had been superseded by Misra and Gries. The original paper finally appeared in the 1991 festschrift for Woody Bledsoe. The authors write that they still consider it a minor landmark in formal verification and automated reasoning, as the first time a new algorithm was presented together with its mechanically checked correctness proof.

Checklist before you use it

  • What majority means: strictly more than n/2. Exactly half is not a majority.
  • The second pass: unless a majority is guaranteed, count the candidate again. The first pass alone produces a candidate even when there is no majority.
  • What the counter means: the final counter is not the candidate’s vote total, only the votes left after cancelling.
  • Comparisons: equality only, so it works for values with no order, but that comparison must be consistent.
  • Scope: this algorithm handles the single element that appears more than half the time. Finding elements that appear more than n/k times is the subject of the Misra–Gries paper mentioned above and is outside the scope of this post.

Sources

All checked on 2026-10-18.

Back to the blog