I've just spent a couple of days tracking this down, so hopefully I can save someone else the trouble.
My problem was that I have data which is sorted by a database query displayed in a grid with ViewType="OutlookGroupBy", and the sorting was getting lost whenever someone grouped a column. Having spent much time trying to fix this by setting sorting on the columns (inefficient, without much success) I finally realised that it's because the default sorting algorithm is QuickSort, which is unstable - which is to say that it does not preserve the original order of elements with the same sort key value.
All that's needed to make this work properly is to set the sort algorithm (either the default sorting algorithm in Display Layout, or at the band or column level) to one of the stable sorting algorithms: BinaryTreeSort, BubbleSort, or InsertionSort.
Just got the answer from our lead WebDataGrid developer - in the new WebDataGrid the sorting will be left to the respective datasource (if the datasource supports that) - so that each individual datasource, say, Linq, Access, Sql, etc will have its own respective best implementation and we will use that. In the cases where the datasource does not support sorting (e.g. simple list) the default sort will be like you suggested BinaryTree - so good news there.
For UltraWebGrid - it is a mature product already used by tens of thousands of developers and it is a bit hard for us to change the default at this point - but we will make sure we have this mentioned somewhere.
Thanks again for the great feedback.
Thanks for the follow-up.
It is good that you bring this up now, since we may consider changing the default sorting to stable for the WebDataGrid control (our next generation Aikido grid control).
BinaryTree and MergeSort are very good options - both stable, and with O(n log n) complexity - the same as QuickSort
InsertionSort I think comes next best for stable, with O(n * n) (and from what I see n * n / 4 in most cases).
Definitely BinaryTree seems the best options for stable sorting.
Thanks again.
QuickSort is a very good algorithm and in many (perhaps most) cases, it's the right choice. Maybe the best approach would simply be to include a page describing the benefits and disadvantages of the various different algorithms available in the documentation, and perhaps add a note to the samples and example code in the Knowledge Base.
Having said that, I'm using BinaryTree with quite a large amount of data and it seems to be performing quite well.
Hello,
Yes, thanks for sharing. This is indeed the case, QuickSort is not stable, e.g. does not guarantee that rows will always be sorted the same way if there are several rows with the same value of the column being sorted. In most cases this is ok, but I do see how this can cause you troubles in your case.
QuickSort is the default sorting algorithm used in .NET in general and is fastest, that is why it is picked as default. Maybe we need to make that more ovbious in help samples... or maybe we can default to another one that is stable and provides similar performance. I have escalated this to our WebGrid dev team - thanks a lot for sharing.