Indexing or sorting ordered arrays.

[Ed Kleban]

When you set the fIndexed EVFlag, then V2 builds an index, correct?
Presumably it uses some sort algorithm to do this.   Similarly when you call
the Vtable.Sort command, it again uses some algorithm to sort.  I am curious
what the algorithm used is, because I would like to know the behavior when
the column of items to index, or the column of items to sort is already
sorted.  I'm curious if when the items are already sorted:

1) Performing a sort on them may be very slow, because QuickSort is used,
and Quicksort has poor performance when used to sort a list that is already
sorted, or...

2)  Performing a sort on them is very fast because a serialization check is
made to see if they are already sorted and if so nothing is done, or...

3) Performing a sort on them is not terrible, because IntroSort is used
instead of QuickSort which has much better worst-case sorting efficiency
when the list is already sorted, or...

4) QuickSort is used, however before it is use several of list elements are
randomly reordered to avoid the performance problems that occur when the
list is already sorted.

5) I'm totally clueless because you're simply not indexing or sorting in any
of these ways.




On 11/20/05 1:18 AM, "Ruslan Zasukhin" <sunshine at public.kherson.ua> wrote:

> On 11/20/05 9:01 AM, "Ed Kleban" <Ed at Kleban.com> wrote:
> 
>> What sorting algorithm does Valentina use?   Is the algorithm similar to
>> Quicksort that will perform poorly when sorting or indexing an array that is
>> already correctly ordered?  Or is it an IntroSort algorithm that degrades
>> nicely?  Or does it randomize a few elements prior to sorting to avoid the
>> Quicksort performance problems?   Or something else?
> 
> Uses where ?