Just as a bit of colour for this post, the three ways query name can be sorted as pointed out by dariober are:
samtools -n: Uses a natural sort. The check in python would be:
def nat(qname): return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', qname)]
it = iter(qnames); it.next()
all(nat(b) >= nat(a) for a, b in itertools.izip(qnames, it))
picard SortSam SORT_ORDER=queryname: Uses an ASCII sort:
it = iter(qnames); it.next()
all(b >= a for a, b in itertools.izip(qnames, it)) # returns True or False accordingly
unix sort: Uses a "dictionary sort" which is unix for "ASCII sort for only alphanumeric values":
def alphanumeric(qname): [ s for s in qnames[0] if s.isalnum() ]
it = iter(qnames); it.next() # always 1 ahead
all(alphanumeric(b) >= alphanumeric(a) for a, b in itertools.izip(qnames, it))
When sorting by position, fortunately samtools and Picard are exactly the same. This is because they don't try and sort the chromosomal order (using the same incompatible method as the qname), but instead use whatever is already in the head of the SAM/BAM file. Since neither tool lets you sort without a header, we get compatibility here :) Also, I think most mappers return the chromosomes in natural-sort order (chr1, chr2, ... chr10), which is nice. Maybe thats just how the genome.fa comes.
With unix's sort -k3,3 -k4,4n however, which you'll see scattered around the place for sorting SAM files, you'll get chromosomes in the same dictionary-sort order as unix sort gives the qnames (chr1, chr10, ... chr2). This of course is a really really bad idea.
