Vista - How does sort work

01-24-2008

In sort-object, what algorithm does PowerShell use for sorting?

A delegate asked me today noting that different algorithms have
different speeds.

Any clues?
--
Thomas Lee
doctordns@xxxxxx
MVP - Admin Frameworks and Security

01-24-2008

"Thomas Lee" <tfl@xxxxxx> wrote in message
news:8UZQAVclZImHFAAj@xxxxxx

Quote:

> In sort-object, what algorithm does PowerShell use for sorting?
>
> A delegate asked me today noting that different algorithms have different
> speeds.
>
> Any clues?

Sort-Object appears to be using the System.Collection.Generic.List<T> type's
Sort method and specifically the one that takes an object that implements
IComparer<T>. Here is what the MSDN docs have to save about this sort
method:

This method uses Array..::.Sort, which uses the QuickSort algorithm. This
implementation performs an unstable sort; that is, if two elements are
equal, their order might not be preserved. In contrast, a stable sort
preserves the order of elements that are equal.

On average, this method is an O(n log n) operation, where n is Count; in the
worst case it is an O(n ^ 2) operation.

--
Keith

01-25-2008

In message <2BD7CC74-1595-4C86-A18C-917C9D44D3FE@xxxxxx>, "Keith
Hill [MVP]" <r_keith_hill@xxxxxx_spam_I> writes

Quote:

>"Thomas Lee" <tfl@xxxxxx> wrote in message
>news:8UZQAVclZImHFAAj@xxxxxx

Quote:

>> In sort-object, what algorithm does PowerShell use for sorting?
>>
>> A delegate asked me today noting that different algorithms have
>>different speeds.
>>
>> Any clues?

>
>Sort-Object appears to be using the System.Collection.Generic.List<T>
>type's Sort method and specifically the one that takes an object that
>implements IComparer<T>. Here is what the MSDN docs have to save about
>this sort method:
>
>This method uses Array..::.Sort, which uses the QuickSort algorithm.
>This implementation performs an unstable sort; that is, if two elements
>are equal, their order might not be preserved. In contrast, a stable
>sort preserves the order of elements that are equal.
>
>On average, this method is an O(n log n) operation, where n is Count;
>in the worst case it is an O(n ^ 2) operation.

Thanks!
--
Thomas Lee
doctordns@xxxxxx
MVP - Admin Frameworks and Security

01-24-2008	#1 (permalink)
Thomas Lee n/a posts	How does sort work In sort-object, what algorithm does PowerShell use for sorting? A delegate asked me today noting that different algorithms have different speeds. Any clues? -- Thomas Lee doctordns@xxxxxx MVP - Admin Frameworks and Security
My System Specs

01-24-2008	#2 (permalink)
Keith Hill [MVP] n/a posts	Re: How does sort work "Thomas Lee" <tfl@xxxxxx> wrote in message news:8UZQAVclZImHFAAj@xxxxxx Quote: > In sort-object, what algorithm does PowerShell use for sorting? > > A delegate asked me today noting that different algorithms have different > speeds. > > Any clues? Sort-Object appears to be using the System.Collection.Generic.List<T> type's Sort method and specifically the one that takes an object that implements IComparer<T>. Here is what the MSDN docs have to save about this sort method: This method uses Array..::.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal. On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation. -- Keith
My System Specs

01-25-2008	#3 (permalink)
Thomas Lee n/a posts	Re: How does sort work In message <2BD7CC74-1595-4C86-A18C-917C9D44D3FE@xxxxxx>, "Keith Hill [MVP]" <r_keith_hill@xxxxxx_spam_I> writes Quote: >"Thomas Lee" <tfl@xxxxxx> wrote in message >news:8UZQAVclZImHFAAj@xxxxxx Quote: >> In sort-object, what algorithm does PowerShell use for sorting? >> >> A delegate asked me today noting that different algorithms have >>different speeds. >> >> Any clues? > >Sort-Object appears to be using the System.Collection.Generic.List<T> >type's Sort method and specifically the one that takes an object that >implements IComparer<T>. Here is what the MSDN docs have to save about >this sort method: > >This method uses Array..::.Sort, which uses the QuickSort algorithm. >This implementation performs an unstable sort; that is, if two elements >are equal, their order might not be preserved. In contrast, a stable >sort preserves the order of elements that are equal. > >On average, this method is an O(n log n) operation, where n is Count; >in the worst case it is an O(n ^ 2) operation. Thanks! -- Thomas Lee doctordns@xxxxxx MVP - Admin Frameworks and Security
My System Specs

Similar Threads
Thread	Forum
IE8 won't sort favorites	Vista General
Re: Can I sort within a sort, in folder view (eg., Name, Date)	Live Mail
Sort by name doesnt sort correctly in my opinion	Vista file management
Column Sort Doesn't Work - Restore File Selection	Vista performance & maintenance
Sort of OT	Vista General