Memory cells of a nonvolatile memory array are characterized by one of multiple threshold voltage ranges including at least an erased threshold voltage range and a programmed threshold voltage range. Responsive to an erase command to erase a group of memory cells of the nonvolatile memory array, a plurality of phases are performed, including at least a pre-program phase and an erase phase. The pre-program phase programs a first set of memory cells in the group having threshold voltages within the erased threshold voltage range, and does not program a second set of memory cells in the group having threshold voltages within the erased threshold voltage range in the group. By not programming the second set of memory cells, the pre-program phase is performed more quickly than if the second set of memory cells were programmed along with the first set of memory cells.