An asynchronous P system for counting sort

Membrane computing, which is a computational model based on cell activity, has attracted considerable attention as a new paradigm in computation. Using membrane computing, several algorithms for elementary operations, such as sorting, have been proposed. However, the proposed algorithms for sorting in membrane computing have different types of inputs. In addition, there is room for improvement on the complexities of the proposed algorithms. In the present paper, we propose an asynchronous P system based on counting sort for inputs representing binary numbers. The proposed P system sorts n binary numbers of m bits in O(mn
²
) sequential steps and O(mn) parallel steps.