The design of optimal multiple description scalar quantizers was pioneered by Vaishampayan with a generalization of Lloyd's algorithm, which alternatively optimizes the decoder, respectively the encoder, while the other component is fixed. We propose an algorithm which speeds up the encoder optimization step from O(N^2) to O(N\log N) time complexity, where N is the number of cells in the central partition.