In this work, a new approach to improve the algorithmic efficiency of the order statistic-constant false alarm rate (OSCFAR) applied in two dimensions (2D) is presented. OS-CFAR is widely used in radar technology for detecting moving objects as well as in sonar technology for the relevant areas of segmentation and multi-target detection on the seafloor. OSCFAR rank orders the samples obtained from a sliding window around a test cell to select a representative sample that is used to calculate an adaptive detection threshold maintaining a false alarm probability. Then, the test cell is evaluated to determine the presence or absence of a target based on the calculated threshold. The rank orders allow that OS-CFAR technique to be more robust to the presence of the speckle noise, but requires higher computational effort. This is the bottleneck of the technique. Consequently, the contribution of this work is to improve the OSCFAR 2D on-line computation with the distributive histograms and the optimal breakdown point optimal concept, mainly from the standpoint of efficient computation. The theoretical algorithm analysis is presented to demonstrate the improvement of this approach. Also, this novel efficient OS-CFAR 2D was contrasted experimentally on acoustic images.