Re: [fpc-devel] Sorting tests
On 11/30/22 08:30, Nikolay Nikolov wrote: On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote: Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. IIRC, Lazarus had a comparison function that returned a Sorry, I meant to say ahttps://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote: Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. IIRC, Lazarus had a comparison function that returned acaused an infinite loop, not a crash. I don't remember the details, you should examine the source control history. The problem was fixed a long time ago in Lazarus, however it was decided not to change the default algorithm, but rather provide a plugable mechanism for changing the algorithm, hence the sortalgs unit provides several different options. FPC developers didn't want to have the bug tracker be filled with bug reports, caused by that (people would first assume it's a bug in the new FPC version if their code fails on a new FPC version, but works in the previous version). Nikolay ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022 23:57:14 + "J. Gareth Moreton via fpc-devel" wrote: > Familarity mostly. More people are familiar with quicksort than > introsort. Are there any explicit code examples where quicksort > succeeds and introsort fails? I'm told even Lazarus crashes (or used > to crash), so I'll be interested to see what code causes (or caused) > it. +1 >[...] Mattias ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Familarity mostly. More people are familiar with quicksort than introsort. Are there any explicit code examples where quicksort succeeds and introsort fails? I'm told even Lazarus crashes (or used to crash), so I'll be interested to see what code causes (or caused) it. If the pivot is one of the values with a duplicate key, then there is a chance that the other identical values will change order, and I don't think there's a fast away to avoid this situation. But if needs be, here's a worked example to show quicksort is not stable, say our data is: 3 2 1 4a 4b 4c 7 5 6 Choosing the median of three gives us 4b. Assuming we're using an "(a < b) = True" comparison to put items into the left partition: [3 2 1 *4b* 4a 4c 7 5 6] Recursing: [1 *2* 3] 4b [4a 4c 5 *6* 7] 1 2 3 4b [*4c* 4a 5] 6 7 (The pivot choice here depends on the order of checking the three values... here it's doing "l < m" (False), "m < r" (True) then "l < r" (True)) 1 2 3 4b 4c 4a 5 6 7 Thus, the middle items are not in the same order. Kit On 29/11/2022 22:58, Mattias Gaertner via fpc-devel wrote: On Tue, 29 Nov 2022 15:54:03 +0100 Benito van der Zander via fpc-devel wrote: Hi, and the FPC implementation is actually documented to not be stable in [...] and one can see that it is indeed not stable, if you sort ['a','b','A'] case-insensitively, it becomes ['A', 'a','b'] If the current QuickSort is not stable, is there an another argument for keeping it as default? Mattias ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022 15:54:03 +0100 Benito van der Zander via fpc-devel wrote: > Hi, > and the FPC implementation is actually documented to not be stable in >[...] > and one can see that it is indeed not stable, if you sort > ['a','b','A'] case-insensitively, it becomes ['A', 'a','b'] If the current QuickSort is not stable, is there an another argument for keeping it as default? Mattias ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/29/22 22:16, J. Gareth Moreton via fpc-devel wrote: On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote: if (a That's the big one that sorting algorithms rely on... the transitive law. If that is violated, then you cannot guarantee a sorted result. It doesn't matter if (a < b) or (b < a) return False for equal elements, or use (a <=b) or (b <= a) instead, as long as it's consistent. Also have to watch out for more subtle instances of it, like "if (a < b) then DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;". While I do wish people would fix any bugs that are found in their own code, sometimes we do have to accept that this isn't always possible. I think the most famous example I can think of is with SimCity 2000... there was a critical bug in it where memory was used after it was deallocated. Under DOS and Windows 3.1, this wasn't an issue because the memory wouldn't be reused by another application, but under Windows 95 this assumption could no longer hold. So, under the guidance of Raymond Chen, Microsoft programmed Windows 95 to delay actually releasing that block of memory... only for SimCity 2000! Yes. Horrible. :) Another example is Quake 2 or 3 (I forgot which one) having a buffer overflow vulnerability, because of copying (strcpy) the OpenGL extensions string to a C fixed size buffer (char buf[1024] or something like that). After a certain point, OpenGL video cards became so advanced and got so many extensions, that the string, returned by the graphics card simply became too long for that buffer, thus causing Quake to crash instantly on startup. But since nobody wants to buy a video card, that doesn't run Quake, graphics card vendors had to implement a hack - the detect the Quake .exe and report a different, shorter, extensions string. Nikolay Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote: if (a That's the big one that sorting algorithms rely on... the transitive law. If that is violated, then you cannot guarantee a sorted result. It doesn't matter if (a < b) or (b < a) return False for equal elements, or use (a <=b) or (b <= a) instead, as long as it's consistent. Also have to watch out for more subtle instances of it, like "if (a < b) then DoX else DoY;" and then having "if (b < a) then DoZ else DoQ;". While I do wish people would fix any bugs that are found in their own code, sometimes we do have to accept that this isn't always possible. I think the most famous example I can think of is with SimCity 2000... there was a critical bug in it where memory was used after it was deallocated. Under DOS and Windows 3.1, this wasn't an issue because the memory wouldn't be reused by another application, but under Windows 95 this assumption could no longer hold. So, under the guidance of Raymond Chen, Microsoft programmed Windows 95 to delay actually releasing that block of memory... only for SimCity 2000! Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/29/22 16:44, Ondrej Pokorny via fpc-devel wrote: Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel: For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. I assume this was some kind of typo or reasoning error because "acompare function is correct. And Nikolay was talking about incorrect comparison functions. Yes, I made a mistake, due to being in a hurry, while writing this email. I meant other properties, such as: (a Ondrej ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
How so? Heapsort isn't stable either. Is there a variant I'm not aware of? Kit On 29/11/2022 16:36, Marco van de Voort via fpc-devel wrote: On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote: This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 Now that I know where Introsort is in the sortalgs.pp unit, I'll see about improving Introsort there too. Regarding a stable sort, what does GCC's "std::stable_sort" use? https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge sort. (The algorithm before it in the video, "std::sort", is introsort, but it postpones doing the insertion sort until the very end, which doesn't work in practice because of caching issues) Usually it is heapsort that is picked as alternative to quicksort if stable algo is needed. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote: This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 Now that I know where Introsort is in the sortalgs.pp unit, I'll see about improving Introsort there too. Regarding a stable sort, what does GCC's "std::stable_sort" use? https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge sort. (The algorithm before it in the video, "std::sort", is introsort, but it postpones doing the insertion sort until the very end, which doesn't work in practice because of caching issues) Usually it is heapsort that is picked as alternative to quicksort if stable algo is needed. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
This is why I hope my own improvement to the version in TArrayHelper could be used instead: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334 Now that I know where Introsort is in the sortalgs.pp unit, I'll see about improving Introsort there too. Regarding a stable sort, what does GCC's "std::stable_sort" use? https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m5s - it resembles merge sort. (The algorithm before it in the video, "std::sort", is introsort, but it postpones doing the insertion sort until the very end, which doesn't work in practice because of caching issues) Kit On 29/11/2022 15:03, Stefan Glienke via fpc-devel wrote: That is not a very good IntroSort to be honest. It is missing using InsertionSort for small numbers and it does not do the median-of-3 pivot selection. Am 29.11.2022 um 09:22 schrieb Nikolay Nikolov via fpc-devel: On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. But IntroSort is already implemented in packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default sorting algorithm, because it breaks existing code that implements an incorrect comparison function. E.g. if you pass a function that returns abehavior will change, when you change the algorithm. This even broke Lazarus, it caused it to hang on startup. Best regards, Nikolay Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
More like a variation of that: TimSort - but that's rather a beast to implement properly and efficient. Am 29.11.2022 um 14:41 schrieb J. Gareth Moreton via fpc-devel: Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)). If you want a stable sort, you need to use things like merge sort instead. Kit On 29/11/2022 13:25, Sven Barth via fpc-devel wrote: Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns aFor such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
That is not a very good IntroSort to be honest. It is missing using InsertionSort for small numbers and it does not do the median-of-3 pivot selection. Am 29.11.2022 um 09:22 schrieb Nikolay Nikolov via fpc-devel: On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. But IntroSort is already implemented in packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default sorting algorithm, because it breaks existing code that implements an incorrect comparison function. E.g. if you pass a function that returns abehavior will change, when you change the algorithm. This even broke Lazarus, it caused it to hang on startup. Best regards, Nikolay Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Hi, and the FPC implementation is actually documented to not be stable in the code: { QuickSort Average performance: O(n log n) Worst performance: O(n*n) Extra memory use: O(log n) on the stack Stable: no Additional notes: Uses the middle element asthe pivot. This makes it work well also on already sorted sequences, which can occur often in practice. As expected from QuickSort, it works best on random sequencesand is usually the fastest algorithm to sort them. It is, however, possible for a malicious user to craft special sequences, which trigger its worst O(n*n)case. They can also occur in practice, although they are veryunlikely. If this is not an acceptable risk (e.g.for high risk applications, security-conscious applications or applications with hard real-time requirements),another sorting algorithm must be used. } and one can see that it is indeed not stable, if you sort ['a','b','A'] case-insensitively, it becomes ['A', 'a','b'] If you want a stable sort, you need to use things like merge sort instead. I wanted a stable sort and implemented merge sort, and it was far too slow to be usable. Now I use the sortbase quicksort, but sort an array of pointers to the actual array, so the compare function can compare the indices for equal elements. Cheers, Benito On 29.11.22 14:41, J. Gareth Moreton via fpc-devel wrote: Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)). If you want a stable sort, you need to use things like merge sort instead. Kit On 29/11/2022 13:25, Sven Barth via fpc-devel wrote: Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns aFor such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Where exactly can that stable quicksort be found? rtl/inc/sortbase.pp looks pretty much like standard quicksort to me. Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel: For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. I assume this was some kind of typo or reasoning error because "acompare function is correct. And Nikolay was talking about incorrect comparison functions. Ondrej ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Quicksort is not inherently stable because of what happens if a value is equal to the pivot - more specifically, which of the identical values is selected as the pivot - for example, if you try to sort a list of identical values, they will inevitably change order because each stage will move all of the values to one side of the pivot (and also cause quicksort to degenerate into O(n²)). If you want a stable sort, you need to use things like merge sort instead. Kit On 29/11/2022 13:25, Sven Barth via fpc-devel wrote: Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns aFor such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "ais the case for equal elements. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Ondrej Pokorny via fpc-devel schrieb am Di., 29. Nov. 2022, 11:39: > Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: > > J. Gareth Moreton via fpc-devel schrieb > am Di., 29. Nov. 2022, 10:09: > >> Surely that's a bug in the comparison functions that should be fixed and >> not something that can be blamed on introsort. If a comparison function >> is faulty, then pretty nuch any sorting algorithm can be considered to >> have unpredictable behaviour. >> > > This *can* be blamed on IntroSort, because Stability (order of equal > elements is kept) is an attribute of sorting algorithms and IntroSort is > *not* considered stable while QuickSort *can* be stable depending on the > implementation and ours *is*. > > If for two elements [a, b] the comparison function returns > a > then the problem is not in stability or any other feature of the sorting > algorithm but in the comparison function indeed. Or am I missing something? > For such a comparison function the issue is indeed in the comparison function, but Nikolay also mentioned "a ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel: J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. If for two elements [a, b] the comparison function returns athen the problem is not in stability or any other feature of the sorting algorithm but in the comparison function indeed. Or am I missing something? Ondrej ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
J. Gareth Moreton via fpc-devel schrieb am Di., 29. Nov. 2022, 10:09: > Surely that's a bug in the comparison functions that should be fixed and > not something that can be blamed on introsort. If a comparison function > is faulty, then pretty nuch any sorting algorithm can be considered to > have unpredictable behaviour. > This *can* be blamed on IntroSort, because Stability (order of equal elements is kept) is an attribute of sorting algorithms and IntroSort is *not* considered stable while QuickSort *can* be stable depending on the implementation and ours *is*. Regards, Sven > ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Hmmm, that's a problem! Fair enough. Kit On 29/11/2022 09:21, Michael Van Canneyt via fpc-devel wrote: On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. No-one is blaming introsort. It's about not breaking other software that depends on the sort mechanisms provided by the RTL. They were documented as using quicksort. Since we don't control the external functions, we cannot set introsort as the default till we know for sure that all external functions are OK with that. We of course could do that and just tell people to fix their implementation. But that's not very friendly. From their point of view, their function is working fine (it may well be for quicksort which was the default mechanism), and we would break it. Michael. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote: Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. No-one is blaming introsort. It's about not breaking other software that depends on the sort mechanisms provided by the RTL. They were documented as using quicksort. Since we don't control the external functions, we cannot set introsort as the default till we know for sure that all external functions are OK with that. We of course could do that and just tell people to fix their implementation. But that's not very friendly. From their point of view, their function is working fine (it may well be for quicksort which was the default mechanism), and we would break it. Michael.___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Surely that's a bug in the comparison functions that should be fixed and not something that can be blamed on introsort. If a comparison function is faulty, then pretty nuch any sorting algorithm can be considered to have unpredictable behaviour. Kit On 29/11/2022 08:22, Nikolay Nikolov via fpc-devel wrote: On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. But IntroSort is already implemented in packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default sorting algorithm, because it breaks existing code that implements an incorrect comparison function. E.g. if you pass a function that returns abehavior will change, when you change the algorithm. This even broke Lazarus, it caused it to hang on startup. Best regards, Nikolay Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. But IntroSort is already implemented in packages/rtl-extra/src/inc/sortalgs.pp. It's just not the default sorting algorithm, because it breaks existing code that implements an incorrect comparison function. E.g. if you pass a function that returns achange, when you change the algorithm. This even broke Lazarus, it caused it to hang on startup. Best regards, Nikolay Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Stefan Glienke via fpc-devel schrieb am Mo., 28. Nov. 2022, 12:39: > In Delphi that would be the > https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind > intrinsic - I could not find that one in the 3.2.0 feature list. > That one is also supported since 3.2.0, though it seems I forgot to add it to the New Features List... Regards, Sven ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
That could work - could be interesting to experiment with. Kit On 28/11/2022 11:43, Stefan Glienke via fpc-devel wrote: Nevermind - I guess there is: https://www.freepascal.org/docs-html/rtl/system/gettypekind.html Am 28.11.2022 um 12:35 schrieb Stefan Glienke via fpc-devel: In Delphi that would be the https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind intrinsic - I could not find that one in the 3.2.0 feature list. Am 28.11.2022 um 11:17 schrieb J. Gareth Moreton via fpc-devel: Well that spoils that idea! Is there any way to determine if it's pointer-based so you can swap references instead of going through the whole penalty of creating and destroying temporary objects? Kit On 28/11/2022 10:07, Sven Barth wrote: J. Gareth Moreton via fpc-devel schrieb am Mo., 28. Nov. 2022, 11:01: Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!) No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Nevermind - I guess there is: https://www.freepascal.org/docs-html/rtl/system/gettypekind.html Am 28.11.2022 um 12:35 schrieb Stefan Glienke via fpc-devel: In Delphi that would be the https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind intrinsic - I could not find that one in the 3.2.0 feature list. Am 28.11.2022 um 11:17 schrieb J. Gareth Moreton via fpc-devel: Well that spoils that idea! Is there any way to determine if it's pointer-based so you can swap references instead of going through the whole penalty of creating and destroying temporary objects? Kit On 28/11/2022 10:07, Sven Barth wrote: J. Gareth Moreton via fpc-devel schrieb am Mo., 28. Nov. 2022, 11:01: Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!) No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
In Delphi that would be the https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind intrinsic - I could not find that one in the 3.2.0 feature list. Am 28.11.2022 um 11:17 schrieb J. Gareth Moreton via fpc-devel: Well that spoils that idea! Is there any way to determine if it's pointer-based so you can swap references instead of going through the whole penalty of creating and destroying temporary objects? Kit On 28/11/2022 10:07, Sven Barth wrote: J. Gareth Moreton via fpc-devel schrieb am Mo., 28. Nov. 2022, 11:01: Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!) No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well. Regards, Sven ___ fpc-devel maillist -fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Well that spoils that idea! Is there any way to determine if it's pointer-based so you can swap references instead of going through the whole penalty of creating and destroying temporary objects? Kit On 28/11/2022 10:07, Sven Barth wrote: J. Gareth Moreton via fpc-devel schrieb am Mo., 28. Nov. 2022, 11:01: Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!) No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well. Regards, Sven ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
J. Gareth Moreton via fpc-devel schrieb am Mo., 28. Nov. 2022, 11:01: > Just want to clarify something... if a type is managed, can it be safely > typecast to a pointer in all instances and on all platforms? (The > purpose being so if I wanted to swap two items, so there's no overall > change in the reference counters, I can simply swap the pointers... > there's no dereferencing involved!) > No, managed does not automatically mean that it's a Pointer based type. Records with management operators, Variants and Windows WideString are managed as well. Regards, Sven > ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
This is something I want to experiment with now. Still waiting on approval of the TArrayHelper sort merge request though before I start playing around with reference counts. Just want to clarify something... if a type is managed, can it be safely typecast to a pointer in all instances and on all platforms? (The purpose being so if I wanted to swap two items, so there's no overall change in the reference counters, I can simply swap the pointers... there's no dereferencing involved!) Kit On 28/11/2022 09:43, Michael Van Canneyt via fpc-devel wrote: On Mon, 28 Nov 2022, Sven Barth via fpc-devel wrote: Stefan Glienke via fpc-devel schrieb am Mo., 28. Nov. 2022, 00:20: Probably not unless FPC has something similar to https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType (that function among a few others is compiletime evaluated). It's supported since 3.2.0: https://wiki.freepascal.org/FPC_New_Features_3.2 And now it is also documented. Tomorrow on the daily docs... Michael. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Mon, 28 Nov 2022, Sven Barth via fpc-devel wrote: Stefan Glienke via fpc-devel schrieb am Mo., 28. Nov. 2022, 00:20: Probably not unless FPC has something similar to https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType (that function among a few others is compiletime evaluated). It's supported since 3.2.0: https://wiki.freepascal.org/FPC_New_Features_3.2 And now it is also documented. Tomorrow on the daily docs... Michael. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Stefan Glienke via fpc-devel schrieb am Mo., 28. Nov. 2022, 00:20: > Probably not unless FPC has something similar to > > https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType > (that function among a few others is compiletime evaluated). > It's supported since 3.2.0: https://wiki.freepascal.org/FPC_New_Features_3.2 Regards, Sven ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Probably not unless FPC has something similar to https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType (that function among a few others is compiletime evaluated). Am 25.11.2022 um 18:57 schrieb J. Gareth Moreton via fpc-devel: Indeed. I'm just trying to think if there's a way that that can be implemented in a cross-platform way, or if there's a wa to identify if a generic type is a pointer/managed type. Kit On 25/11/2022 16:00, Stefan Glienke via fpc-devel wrote: >From experience I can tell that IntroSort is fast enough. The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting. On 24/11/2022 19:51 CET J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
Indeed. I'm just trying to think if there's a way that that can be implemented in a cross-platform way, or if there's a wa to identify if a generic type is a pointer/managed type. Kit On 25/11/2022 16:00, Stefan Glienke via fpc-devel wrote: >From experience I can tell that IntroSort is fast enough. The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting. On 24/11/2022 19:51 CET J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
From experience I can tell that IntroSort is fast enough. The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting. > On 24/11/2022 19:51 CET J. Gareth Moreton via fpc-devel > wrote: > > > Hi everyone, > > I just need to touch on the knowledge base. What tests exist that test > the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm > looking at creating Introsort for this unit as well, but I need to know > if such a unit already exists or if I need to make my own. > > Also, since Olly mentioned that the unit is used in TStringList, it > makes me wonder if the RTL has a radix sort algorithm available, since > radix sort is on the order of O(n) and is ideal for sorting large arrays > of strings (although it can be memory-intensive). > > Kit > > ___ > fpc-devel maillist - fpc-devel@lists.freepascal.org > https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
These are nice but don't actually use the code in rtl/inc/sortbase.pp - maybe they can be adapted though. Kit On 25/11/2022 10:10, Marco Borsari via fpc-devel wrote: On Thu, 24 Nov 2022 18:51:12 + "J. Gareth Moreton via fpc-devel" wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Some times ago I wrote a couple of merge sort routines to use in BWT, the project never goes further so they remain at level of numerical values input only. They should have a good worst case scenario. In the merge.pas the parameter nrm has to be false when the dimension of the array is not a power of two. There also is a check head-tail of the blocks to move in a single pass the smaller one. The natural.pas is recursive in the initial division in blocks and allow for adaptation for inputs already sorted. If you find them useful, you are free to made anything you want. Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Thu, 24 Nov 2022 18:51:12 + "J. Gareth Moreton via fpc-devel" wrote: > Hi everyone, > > I just need to touch on the knowledge base. What tests exist that test > the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm > looking at creating Introsort for this unit as well, but I need to know > if such a unit already exists or if I need to make my own. Some times ago I wrote a couple of merge sort routines to use in BWT, the project never goes further so they remain at level of numerical values input only. They should have a good worst case scenario. In the merge.pas the parameter nrm has to be false when the dimension of the array is not a power of two. There also is a check head-tail of the blocks to move in a single pass the smaller one. The natural.pas is recursive in the initial division in blocks and allow for adaptation for inputs already sorted. If you find them useful, you are free to made anything you want. Marco -- Simplex sigillum veri PROGRAM Sort; CONST len=20; VAR a:ARRAY[0..2*len-1] OF Byte; i,j:Word; src:Boolean; PROCEDURE MergeSort(VAR src:Boolean;nrm:Boolean); VAR dbl,sub,i,j,k,l,m,n,dst,lim:Word; x,y,z:Integer; BEGIN dbl:=len SHL 1; sub:=1; WHILE subdbl THEN l:=dbl; IF m>dbl THEN m:=dbl; IF lim>len THEN lim:=len; END ELSE BEGIN IF l>len THEN l:=len; IF m>len THEN m:=len; IF lim>dbl THEN lim:=dbl; END; x:=l-i; y:=m-j; z:=m-i; END; IF a[l-1]<=a[j] THEN BEGIN IF z>0 THEN Move(a[i],a[dst],z); i:=l; j:=m; dst:=lim; END (* Solo < per avere un metodo stabile *) ELSE IF a[m-1]0 THEN Move(a[j],a[dst],y) ELSE y:=0; IF x>0 THEN Move(a[i],a[dst+y],x); i:=l; j:=m; dst:=lim; END; WHILE dst=m) OR ((iPROGRAM Sort; CONST len=20; VAR a,b:ARRAY[0..len-1] OF Byte; h,t,idx:Word; PROCEDURE NaturalSort(i,j,k:Word;run:Byte); VAR l,m:Word; BEGIN l:=i; m:=j; IF run<>2 THEN BEGIN t:=a[i]; Inc(i); h:=a[i]; WHILE (i<=m) AND (h>=t) DO BEGIN t:=h; Inc(i); h:=a[i]; END; Dec(i); END ELSE i:=k; IF i1 THEN BEGIN h:=a[j]; Dec(j); t:=a[j]; WHILE (j>=l) AND (h>=t) DO BEGIN h:=t; Dec(j); t:=a[j]; END; Inc(j); END ELSE j:=k; IF i-l>=m-j THEN BEGIN k:=i+1; NaturalSort(k,m,j,1); j:=k; END ELSE BEGIN k:=j-1; NaturalSort(l,k,i,2); i:=k; END; END ELSE k:=len; IF ki) OR (a[l]<=a[j]) THEN Inc(l) ELSE BEGIN b[h]:=a[l]; Inc(h); a[l]:=a[j]; Inc(l); Inc(j); END ELSE BEGIN IF l<=i THEN BEGIN b[h]:=a[l]; Inc(h); END; IF (j>m) OR (b[t]<=a[j]) THEN BEGIN a[l]:=b[t]; Inc(l); Inc(t); END ELSE BEGIN a[l]:=a[j]; Inc(l); Inc(j); END; END; END; END; BEGIN Randomize; FOR idx:=0 TO len-1 DO BEGIN a[idx]:=Random(256); Write(' ',a[idx]); END; WriteLn; NaturalSort(0,len-1,len,0); FOR idx:=0 TO len-1 DO Write(' ',a[idx]); END. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Sorting tests
Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel