The End-User experience for multiple column sort is awful. Please provide a UI that lets them see & change the columns they are sorting by. 

Current problems are: 
1. If the user is sorting by 3 columns. All they see is 3 columns with an up/down arrow. There is no visual indication of the actual sort order (Col1, Col2, Col3) or (Col2, Col3, Col1). 

2. Lack of Control.
This gets more confusing if you have 3 columns in a sort, then  click Col2, until it is not sorted. Then click it again to make it sort ascending. I assume it drops out of the sort, & is then added at the end. Making sort =  (Col1, Col3, Col2). 
This confusion forces you to clear everything & start the sort again. 

3. Inability to clear quickly. 
But there is no UI that offers the user a quick way to Unselect all sorted cols, so they can start the sort selection process again. Clearly we can add something to the toolbar, but ideally they wouldn't need to clear & restart their sort selection. . 

4. Unpredictable outcome.
It is not obvious to the User how to control the order of the multi-column sort. How does the sort get determined? :-
A. First column selected becomes the Primary order, the next col is the Secondary order. 
	eg: select Col1, then col2, then col3, to get (Col1, Col2, Col3) order. 
OR
B. Last column selected is the Primary. 
	eg: select Col3 then col2, then col1 to get (Col3, Col2, Col1) order.

5. Server/Database cost. 
Sorting & network round trips are expensive. Toggling from Asc / Desc / Clear. Is expensive & slow compared to setting all the columns once & clicking OK. 

6. I'd add a mockup image, but this feedback screen doesn't permit uploads. To get an idea of a potential UI, Try sorting on multiple columns in Excel. It shows like a tree, with the primary key at the top, the secondary a line lower, followed by the less significant keys below it. 
OR at min. Change the Arrow into an Arrow with a tiny number (1,2,3 etc)
7. The current approach you use to add the Sort icon is really annoying to the user, especially when they have many narrow columns of numbers. Be aware that when you add the sort icon, converting a Label into something with 3 "..." chars is unnecessary. We found it cleaner to just truncate the chars that didn't fit, the user gets to see 2 more letters of the label. Which may be enough for them to know which column it is. And it is obvious that the column was too small to display more text. 
The large padding to the left of the "ColumnMenu" icon is part of the problem, it could be much smaller. 0.5 to 0.25 char width is sufficient. 
We did a lot of usability testing around this for a different control. The outcome was nearly unanimous in favor of the change above. 

PS: I too could see benefit in having the sort indicator display to the left. But the changes above may reduce the need a bit..