Satellite image segmentation is challenging due to the presence of weakly correlated and ambiguous multiple regions of interest. Several bio-inspired algorithms were developed to generate optimum threshold values for segmenting such images efficiently. Their exhaustive search nature makes them computationally expensive when extended to multilevel thresholding. In this paper, we propose a computationally efficient image segmentation algorithm, called CSMcCulloch, incorporating McCulloch's method for levy flight generation in Cuckoo Search (CS) algorithm. We have also investigated the impact of Mantegna's method for levy flight generation in CS algorithm (CSMantegna) by comparing it with the conventional CS algorithm which uses the simplified version of the same. CSmantegna algorithm resulted in improved segmentation quality with an expense of computational time. The performance of the proposed CSMcCulloch algorithm is compared with other bio-inspired algorithms such as Particle Swarm Optimization (PSO) algorithm, Darwinian Particle Swarm Optimization (DPSO) algorithm, Artificial Bee Colony (ABC) algorithm, Cuckoo Search (CS) algorithm and CSMantegna algorithm using Otsu's method, Kapur entropy and Tsallis entropy as objective functions. Experimental results were validated by measuring PSNR, MSE, FSIM and CPU running time for all the cases investigated. The proposed CSMcCulloch algorithm evolved to be most promising, and computationally efficient for segmenting satellite images. Convergence rate analysis also reveals that the proposed algorithm outperforms others in attaining stable global optimum thresholds. The experiments results encourages related researches in computer vision, remote sensing and image processing applications. (C) 2016 Elsevier Ltd. All rights reserved.