In this paper we present an algorithm for the 2-weight batching problem: given n 1 jobs with weight w 1 , and n 2 jobs with weight w 2 , all having processing time p, and given a batch setup time Δ, find a sequence of batches of jobs such that the weighted sum of the n = n 1 + n 2 job completion times is minimized. The algorithm has running time O(n log n) when p and Δ are fixed; previously, the fastest known algorithm for this problem had running time O(n). Various properties of optimal solutions are exploited to reduce the problem to one of finding the minimum entry in a certain matrix. Since this matrix has some strong structural properties, its minimum entry can be found in time that is a sublinear function of the matrix size.