<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>More like a variation of that: TimSort - but that's rather a
beast to implement properly and efficient.<br>
</p>
<div class="moz-cite-prefix">Am 29.11.2022 um 14:41 schrieb J.
Gareth Moreton via fpc-devel:<br>
</div>
<blockquote type="cite"
cite="mid:4869ed42-afc4-321a-e2ed-efbe051b0f45@moreton-family.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<p>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.</p>
<p>Kit</p>
<div class="moz-cite-prefix">On 29/11/2022 13:25, Sven Barth via
fpc-devel wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAFMUeB9f5-cFxQTXxffvNAPb1XJW9EzmG+wN=zGjxHnZ1tA7Ww@mail.gmail.com">
<meta http-equiv="content-type" content="text/html;
charset=UTF-8">
<div dir="auto">
<div>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Ondrej Pokorny via
fpc-devel <<a
href="mailto:fpc-devel@lists.freepascal.org"
moz-do-not-send="true" class="moz-txt-link-freetext">fpc-devel@lists.freepascal.org</a>>
schrieb am Di., 29. Nov. 2022, 11:39:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<div>Am 29.11.2022 um 11:08 schrieb Sven Barth via
fpc-devel:<br>
</div>
<blockquote type="cite">
<div dir="auto">
<div>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">J. Gareth
Moreton via fpc-devel <<a
href="mailto:fpc-devel@lists.freepascal.org"
target="_blank" rel="noreferrer"
moz-do-not-send="true"
class="moz-txt-link-freetext">fpc-devel@lists.freepascal.org</a>>
schrieb am Di., 29. Nov. 2022, 10:09:<br>
</div>
<blockquote class="gmail_quote"
style="margin:0 0 0 .8ex;border-left:1px
#ccc solid;padding-left:1ex">Surely that's a
bug in the comparison functions that should
be fixed and <br>
not something that can be blamed on
introsort. If a comparison function <br>
is faulty, then pretty nuch any sorting
algorithm can be considered to <br>
have unpredictable behaviour.<br>
</blockquote>
</div>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">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*.</div>
</div>
</blockquote>
<p>If for two elements [a, b] the comparison function
returns<br>
a<b=true and b<a=true</p>
<p>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?</p>
</div>
</blockquote>
</div>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">For such a comparison function the issue is
indeed in the comparison function, but Nikolay also
mentioned "a<b=false and b<a=false" which is the case
for equal elements. </div>
<div dir="auto"><br>
</div>
<div dir="auto">Regards, </div>
<div dir="auto">Sven </div>
<div dir="auto">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex"> </blockquote>
</div>
</div>
</div>
<br>
<fieldset class="moz-mime-attachment-header"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
fpc-devel maillist - <a class="moz-txt-link-abbreviated moz-txt-link-freetext" href="mailto:fpc-devel@lists.freepascal.org" moz-do-not-send="true">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel" moz-do-not-send="true">https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
<br>
<fieldset class="moz-mime-attachment-header"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
fpc-devel maillist - <a class="moz-txt-link-abbreviated" href="mailto:fpc-devel@lists.freepascal.org">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
</body>
</html>