I did some comparing between the sorting routines i know (I added Kedaman's Sort_Shell method, I didn't know that one yet).
I sorted an array of 10000 strings which were all 50 characters long.
These are the results:
Bubble sort : 83.77213 secs
Selection sort : 50.87294 secs
Sort Shell : 0.9384375 secs
Quick sort : 0.2765 secs

So I would go for quick sort.

P.S. I used my PII 400 MHz and the compiled vb app.