Secure multi-party computation (SMC) is a focus in the international cryptographic community in recent years. Sorting is a basic data operation and a basic problem of algorithm design and analysis. Secure multiparty sorting is the generalization of the millionaires' problem and a basic problem of SMC. It can be extensively used in scientific decision-making, e-commerce recommendation, electronic auction and bidding, anonymous voting and privacy-preserving data-mining, etc. Most existing solutions to sorting problem are applicable to the cases that the private data is known and small. If the data range is not known, they do not work. If the data range is very large, they will be very inefficient. Unfortunately, in practice, many application scenarios fall in these categories. To privately sort data in scenarios that data range is unknown or the data range is very large, two protocols are proposed first for these scenarios where the data range is small or is known to preserve the privacy of data:the scheme where the same data occupy the same order and that where the same data occupy different orders. Then, these protocols are used as building blocks to design schemes to solve the sorting problem in scenarios that data range is unknown or the data range is very large. The proposed new secure sorting protocols can be used as building blocks to solve many practical problems that inherently need sorting. Based on these protocols, a secure and efficient Vickrey auction protocol is designed. Encoding technique and threshold decryption ElGamal cryptosystem are flexibly used to design these protocols. Using the simulation paradigm, it is proved that the protocols are secure in the semi-honest model. Finally, the efficiency of the protocols are tested. The experimental results show that the proposed protocols are efficient.