This letter considers a non-orthogonal multiple access (NOMA) based cooperative relay sharing (CRS) network, where two sources communicate with their corresponding users over the same time and frequency via a shared decode-and-forward relay. A novel transmission scheme using max-min criterion based dynamic decoding order strategy is proposed to minimize the outage probability of the network at the cost of lower complexity and overhead. The closed-form expression of the overall outage probability for the proposed scheme is derived. Both analytical and simulation results show that the proposed scheme can achieve non-zero diversity order and almost the same outage performance as the dynamic power allocation based transmission scheme for NOMA based CRS networks.