Cancellable Sort in .NET ?

Question

Hi

I'm using ListView in VirtualMode to show extremely big number of rows, millions of rows. The data of the rows stored in a Generic List.

Now i want implement a sort feature, that will sort the List by some Comparer.

The problem is that for now, an average single sort takes around 30 seconds, and during this time the user cannot do anything with the ListView and have to wait until it ends.

Not every user will accept to wait that much time, most of users would cancel the sort, if they could, and i want to allow that cancel feature. Unfortunately, the built-in List.Sort cannot be cancelled nor Array.Sort.

For now the sort occurring on separate thread, so I could use Thread.Abort, but it probebly will result in corrupted List, unacceptable for me.

Is there something i can do except reimplement the whole Sort algorithm by myself?

thanks.

Answer 1

Copy the list, sort the copy in a thread then replace the original list (if the sort completes without getting interrupted).

But I'd go with Martinho's suggestion if possible - having the millions of rows in the application to begin with feels wrong to me. Databases can do a far better job of filtering and sorting data before it gets to you.

Answer 2

If you need possibility to cancel sort then you have to create a separate thread. You can prevent corrupting of the original list by reating it's copy and sorting the copy. If user doesn't cancel sorting just exchange original list wist sorted one.

Answer 3

depending completely upon the environment in question - one approach is to let the user cancel waiting for the sort (which is running on a separate thread) but you secretly continue sorting the list in the background and then tell them when its finished with a subtle notification.

Answer 4

There are several ways you could do this. I might write a class that uses the standard BeginXXX/EndXXX asynchronous pattern with a special CancelXXX method. I have left out a lot of code, but I think there is enough here to make the point. Unfortunately with this method you would have to code your own sorting algorithm.

public class Sorter
{
  public IAsyncResult BeginSort(IList<T> values, AsyncCallback complete)
  {
    MyAsyncResult asyncResult = new MyAsyncResult();
    Thread t = new Thread(() =>
      {
        // Implement your sorting algorithm here.
        // Periodically check asyncResult.Cancel at safe points.
        asyncResult.Complete();
        if (complete != null)
        {
          complete(asyncResult);
        }
      });
    t.Start();
    return asyncResult;
  }

  public void EndSort(IAsyncResult asyncResult)
  {
    MyAsyncResult target = asyncResult as MyAsyncResult;
    if (target == null)
    {
      throw new ArgumentException();
    }
    // Add code here to extract any additional information from the IAsyncResult that 
    // you might want to return to the client. Perhaps this method will be empty.
  }

  public void CancelSort(IAsyncResult asyncResult)
  {
    MyAsyncResult target = asyncResult as MyAsyncResult;
    if (target == null)
    {
      throw new ArgumentException();
    }
    target.Cancel = true;
  }

  private class MyAsyncResult : IAsyncResult
  {
    private volatile bool m_Cancel = false;

    public bool Cancel
    {
      get { return m_Cancel; }
      set { m_Cancel = value; }
    }

    public void Complete()
    {
      // Add code here to mark this IAsyncResult as complete.
    }
  }
}

Answer 5

I had a similar problem. Beating the framework Array.Sort is not easy, and using Thread.Abort is not recommended at all. I decided sort operation would not be cancel-able, however I thought about this solution ( did not test it)

Implements your own comparer able to access your IAsyncResult object having a CancelRequested bool field. Before any comparison, check the bool, true throws an exception cought in your your bground thread. No thread abort e.g. any lock can be released correctly. Your initial items are safe. But you still need to build an array, either of ref or of keys indexing your original items, because throwing while comparing may leave the array corrrupted. I guess it is not the case but there's no guaranty for this.

Hope this helps