Array.Sort – which algorithm? (just curious)

General
1

I needed to implement a sorting method for my current project in order to sort an array of objects by a certain string property. As there is no sorting method for objects in Xojo I began toying around with several sorting algorithms (and I am anything but an expert on this).
In order to test my algorithms I splitted a document of 10797 words to a string array and let my sorting methods sort it. I tried the following methods (I am not sure if my English is appropriate for the following descriptions):

  1. A simple bubble sort (for comparison)

  2. A kind of selection sort, which loops through the original array and after each run appends the minimum element to a temporary array before removing it from the original array, so that the original array shrinks with each loop run

  3. A recursive merge sort

  4. A hybrid merge sort with an insertion sort „firing“ if the length of the current sub array (is that a correct term for a part of an array?) is <= 10

  5. Xojo’s Array.Sort method (for comparison)

The sorting durations were:

1. BubbleSort > 14962 milliseconds 2. My SelectionSort > 4450 milliseconds 3. MergeSort > 27 milliseconds 4. MergeSortHybrid > 24 milliseconds 5. Xojo’s Array.Sort > 10 milliseconds

As you can see, the hybrid merge sort is already quite fast (and surely fast enough for my needs) but still not half as fast as Xojo’s Array.Sort method.
So just out of curiosity: Which sorting algorithm does Xojo use for arrays?

Thanks in advance!

2

Why not use Array.SortDelegate instead?

3

Probably quicksort

4

@Eli Ott:I didn’t know that one, thanks! I’ll give it a try…

5

I just tested sorting objects with Array.SortDelegate, and it seems nearly as fast as a genuine Array.Sort with Strings and still considerably faster than my hybrid merge sort. Thanks for the hint (though it has been very interesting for me to dig through different sorting algorithms, so no time wasted)!

6

I always just build a string array out of the property values and use Array.SortWith to sort the array of objects. Of course, that approach predates SortDelegate.

7

radix sort :stuck_out_tongue:
its one that is underused but for certain kinds of data, like strings, can be very fast

8

Thanks for the information! I’ll have a look at it