Multilevel image thresholding is a complex task in image processing as it requires determining more than one thresholds, mostly using meta-heuristics. In popular entropy-based multilevel image thresholding techniques, the major challenges include computing the appropriate value of the entropic parameter automatically from image data and evaluating the performance of an algorithm in the absence of ground-truth images. The paper presents a new algorithm utilizing normalized sum of absolute differences metric. By selecting four different optimization methods and four entropy measures, sixteen variants of the proposed algorithm are developed. A large-scale performance analysis is conducted using 753 images from diverse domains consisting of a total of 48192 experiments. It is observed that SAD metric based new variants provide better performance in the absence of ground-truth images at the cost of slightly higher computation time.