Feedforward Neural Networks with a Rectified Linear Unit (ReLU) activation function is a computational model that is used a lot for solving various practical problems. Most times these neural networks are obtained by machine learning on data and therefore output an estimation of the correct value which is to be computed. Recently, Hertrich and Sering introduced the concept of Max-Affine Arithmetic Programs and showed equivalence between them and neural networks concerning natural complexity measures. We first present their findings for accurately computing the value of a minimum spanning tree of an undirected graph with 𝑛 vertices from its edge weights using a neural network (with fixed weights and biases) of size 𝒪︀(𝑛3 ) by proving the correctness of Hertrich and Sering’s MAAP. Then we explore the use of neural networks for building sorting networks and show that there is a neural network (with fixed weights and biases) of size 𝒪︀(𝑛 log2 𝑛) that sorts 𝑛 = 2𝑘 natural numbers which we do by developing and proving a MAAP that implements Batcher’s odd-even mergesort architecture.