This paper proposes the use of parallel approximate sorting network techniques on Non-Binary LDPC decoding in terms of performance and complexity. Motivated by the messages truncation concept of the Extended Min Sum algorithm and the reduction it induces on the decoding complexity, we seek for an approximate parallel sorting strategy for the Elementary Check Node Unit (ECN) processing of the Extended Min Sum algorithm. We quantify the impact of parallel approximate sorting on both error correction decoding performance and the hardware complexity. Bubble check sorting methods are compared to proposed parallel approximate sorting techniques in terms of BER vs.noise plots. Furthermore hardware synthesis results are provided to demonstrate the effects of parallel sorting networks on area and throughput. It is found that in certain cases of practical interest, a modest degradation of 0.2 dB in coding gain is imposed;however due to proposed parallel approximate sorters, the latency of ECN can be reduced by up to a factor of two or be logarithmic to the input sequence length, in certain architectures