Assuming read pairs have the same name, you can sort the BAM by read name with samtools:

samtools sort -n in.bam -o > out.bam

If you are using Picard , you can sort by queryname.

Copy and pasting from Picard's manual:

SortSam

USAGE: SortSam [options]

Documentation: http://picard.sourceforge.net/command-line-overview.shtml#SortSam

Sorts the input SAM or BAM.

Input and output formats are determined by file extension.

Option Description

INPUT=File The BAM or SAM file to sort. Required.

OUTPUT=File The sorted BAM or SAM output file. Required.

SORT_ORDER=SortOrder Sort order of output file Required. Possible values: {unsorted, queryname, coordinate}