The performance of the client sorting depend mostly from the performance of the JavaScript, so depend on the browser which you use. For example Google Chrome is much better as IE6 in the JavaScript performance. In any way you should understand that your requirement client side instead of the server side makes the sorting at least 1000 times slowly. Is it really what your customer want?

Do you use at least client side paging? It can improve the performance dramatically. Look at the old demos this and this and compare the sorting performance. Which web browser you use? Do you use gridview: true