Click here to Skip to main content
11,719,185 members (79,552 online)
Click here to Skip to main content
Articles » Languages » C# » Applications » Revisions

Fast List<String> Sort in C#

, 4 Jul 2012 CPOL 39.2K 1.1K 44
Rate this:
Please Sign up or sign in to vote.
How to get faster sorting in List(T) string collections
This is an old version of the currently published article.

Introduction

While searching for how to speed up string sorting in .NET collections, I came across this article: Fast String Sort in C# and F# 

I downloaded the StringSort class from the article, tested the speed, and found it sorts 50,000 strings in about 60% less time than the Generic IEnumerable object sorting methods.

So, to build on the previous project by Stefan Savev 2, I have derived a new sfList class from List<string>.

Using the code 

For your List<string> objects, you simply use sfList instead. The only thing that is different is the method it uses to sort strings.
using System;
using System.Collections.Generic;
using Sorting.CSharpStringSort;

namespace SortTests.Sorting
{
  public class sfList : List<string>
  {
    public sfList() : base() { }

    public sfList(int size) : base(size) { }

    public sfList(IEnumerable<String> aArray) : base(aArray) { }

    public new void Sort()
    {
      //StringSort.Sort(this);
      string[] a = this.ToArray();
      this.Clear();
      //sort array and refill contents of this (faster than directly sorting List)
      StringSort.Sort(ref a);
      this.AddRange(a);
    }
  }
}

From my initial testing, I could see that it is faster to copy the List to a string[], clear the list, sort the array using StringSort.Sort and refill the list with the result. This is what is done by replacing the List.Sort method with my call to StringSort.Sort. A very small amount of time is used to do the two extra copies compared to the sort time.

I also tried an overload that allows direct sorting by calling StringSort.Sort(this), but this was around 25% slower (best case).

The only required modification to the StringSort class is to add this method overload for in-place Sort on string[]:

public static void Sort(ref string[] inout)
{
    InPlaceSort(inout, 0, 0, inout.Length);
}

I put the ref in it just to make it a unique signature to overload. The original method returns a sorted copy. I also added a bunch of overloads for testing times for various sorts, but these are not required.

Stopwatch Tests

Ticks to sort copy ------------ 132206
Ticks to sort aArray ---------- 111181
Ticks to Sedgewick Sort bArray: 108932
Ticks to sort sList ----------- 196452
Ticks to List.Sort() sList2 --- 288872
Ticks to sfList.Sort() sList3 - 122279

So from these elapsed tick tests, you can see that List.Sort() (original Microsoft sort) is very slow. The difference between Sedgewick and StringSort is insignificant. Sorting any List seems to have a big overhead compared to string[]. Replacing List.Sort() in a derived class yields the best solution.

History

First published July 4, 2012

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Dan Randolph
Software Developer (Senior) Delcan
United States United States
Dan Randolph is currently a Web Applications Developer with Delcan. Mr. Randolph has a B.S. dergee in Computer Science from the University of Wyoming. He is an active member of the Denver Visual Studio User Group. You can find him posting in the forums on [code.]msdn.microsoft.com and Code Project.

You may also be interested in...

Comments and Discussions


Discussions posted for the Published version of this article. Posting a message here will take you to the publicly available article in order to continue your conversation in public.
 
QuestionLets be honest... Pin
SledgeHammer0127-Aug-12 13:25
memberSledgeHammer0127-Aug-12 13:25 
AnswerRe: Lets be honest... Pin
Dan Randolph27-Aug-12 18:08
memberDan Randolph27-Aug-12 18:08 
GeneralMy vote of 4 Pin
Vitaly Tomilov18-Jul-12 8:34
memberVitaly Tomilov18-Jul-12 8:34 
GeneralRe: My vote of 4 Pin
Dan Randolph18-Jul-12 10:02
memberDan Randolph18-Jul-12 10:02 
Questionnice Pin
CIDev18-Jul-12 5:07
memberCIDev18-Jul-12 5:07 
QuestionClear after sort safer? Pin
Paul @ The Computer Station12-Jul-12 23:14
groupPaul @ The Computer Station12-Jul-12 23:14 
AnswerRe: Clear after sort safer? Pin
Dan Randolph14-Jul-12 4:46
memberDan Randolph14-Jul-12 4:46 
GeneralRe: Clear after sort safer? Pin
Paul @ The Computer Station15-Jul-12 23:03
groupPaul @ The Computer Station15-Jul-12 23:03 
GeneralRe: Clear after sort safer? Pin
Paulo Zemek23-Aug-12 6:57
mvpPaulo Zemek23-Aug-12 6:57 
AnswerRe: Clear after sort safer? Pin
Dan Randolph23-Aug-12 13:21
memberDan Randolph23-Aug-12 13:21 
GeneralRe: Clear after sort safer? Pin
Paulo Zemek23-Aug-12 14:13
mvpPaulo Zemek23-Aug-12 14:13 
GeneralRe: Clear after sort safer? Pin
Dan Randolph23-Aug-12 16:57
memberDan Randolph23-Aug-12 16:57 
GeneralRe: Clear after sort safer? Pin
Paulo Zemek24-Aug-12 3:31
mvpPaulo Zemek24-Aug-12 3:31 
GeneralRe: Clear after sort safer? Pin
Paulo Zemek24-Aug-12 3:37
mvpPaulo Zemek24-Aug-12 3:37 
GeneralRe: Clear after sort safer? Pin
Dan Randolph28-Aug-12 4:20
memberDan Randolph28-Aug-12 4:20 
GeneralRe: Clear after sort safer? Pin
Paulo Zemek28-Aug-12 4:40
mvpPaulo Zemek28-Aug-12 4:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150901.1 | Last Updated 4 Jul 2012
Article Copyright 2012 by Dan Randolph
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid