You can create a script that stores everything in memory, or you can apply the Schwartz transform. . Here is a brief attempt to do the latter.
Change the file rto a sedscript that prints the index number for each match:
/1/s/^/00001 /
/2/s/^/00002 /
Use sedinstead grepand sort by prefix; then cancel the prefix.
sed -f r t | sort -n | cut -d ' ' -f2- >output
sed script ; Awk script (, !)
awk '{ printf("/%s/s/^/%05i /\n", $0, NR) }' r >r.sed
, . , /foo/ \:foo:, , , , , , .
sed script ( , Linux sed ), ;
awk '{ printf("/%s/s/^/%05i /\n", $0, NR) }' r |
sed -f - t | sort -n | cut -d ' ' -f2- >output