I wanna make sure that I understand you correctly, cuz my answer will be subject to my understanding. When you say you have a document that you wanna sort, I believe you meant you wanna sort a documentList.
I have used IDataUtil.sortIDataArrayByKey and it worked just fine for me. In fact, I was on my way to create a Java service for that - using a quick sort (which I had earlier used to sort a string list), but then realized that I was reinventing the wheel. Writing a Java service of your own is obviously one way to go, but if your requirement is as simple as you have put in your post, I think the sortIDataArrayByKey should take care of it.
If you are sure that it isn’t working for you, post your sample data and I can try it out n let you know.