<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type"/>
<title></title>
</head>
<body>
<p style="margin: 0px;"><span> </span></p>
<p style="margin: 0px;"> </p>
<div style="margin: 5px 0px 5px 0px;">
Marco van de Voort <marcov@stack.nl> hat am 24. Mai 2011 um 18:53 geschrieben:<br/>
<br/>
> In our previous episode, Uffe Kousgaard said:<br/>
> > > Why is TimSort specially interesting to you ?<br/>
> ><br/>
> > If it is the best all-purpose sorting algorithm and now the standard in<br/>
> > several other programming languages, it should be obvious why it is also<br/>
> > worth looking at for pascal / delphi developers.<br/>
><br/>
> A quick look at wikipedia will show that timsort has a disadvantage too. It<br/>
> needs up to N records memory, not just Log(n) records like e.g. Quicksort.
</div><br/>
It *can* be implemented to need only log(n). But the current fpc implementation of QuickSort seems to need O(n) memory on the stack.<br/>
<br/>
TimSort needs up to N/2 pointer, which is better than a simple MergeSort.<br/>
<br/>
Mattias<br/>
<br/>
</body>
</html>