I'm sorry that my answer is not a Perl based but if the only thing you want to do is sort the lines based on the first column here is a simpler solution for you:

cat data-file.txt |sed 's/^Cluster//'|sort -k1 -n|sed 's/^\([0-9]\+\)/
+Cluster\1/' > sorted-data.txt
[download]

Here is the output with pasted a few times your test data:

$ cat dd |sed 's/^Cluster//'|sort -k1 -n|sed 's/^\([0-9]\+\)/Cluster\1
+/'| cut -c 1-20
Cluster5        SP_1003(con
Cluster5        SP_1003(con
Cluster5        SP_1003(con
Cluster6        SP_0917(pil
Cluster6        SP_0917(pil
Cluster6        SP_0917(pil
Cluster7                spr_1379(A
Cluster7                spr_1379(A
Cluster7                spr_1379(A
Cluster8                spr_0324(T
Cluster8                spr_0324(T
Cluster8                spr_0324(T
Cluster9        SP_0733(hyp
Cluster9        SP_0733(hyp
Cluster9        SP_0733(hyp
Cluster10       SP_0042(co
Cluster10       SP_0042(co
Cluster10       SP_0042(co
[download]

I hope I have helped.