The challenge of maintaining confidentiality of stored data in cloud is of vital importance to realize the potential of cloud computing. Storing data in encrypted form may solve the problem, but increases the security issues. Performing operations on cloud data requires repeated decryption-encryption which lessens the meaning of cloud. Hence, Fully homomorphic encryption (FHE) is an effective scheme to support arbitrary operations directly on encrypted data. It is propose the implementation of various algorithms that sort data encrypted with Fully Homomorphic Encryption scheme. The technique is obtained by focusing on the multiplicative depth of the sorting circuit along with the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows significant reduction in the growth of noise resulting in approximately 50% efficiency savings. It is first to consider a number of well known comparison based sorting algorithms as well as some sorting networks, and analyze their circuit implementations with respect to multiplicative depth.