I have a script that currently sorts a multi-dimensional array by multiple fields so that in the end all of the elements of the array are sorted by field a, then by field b within field a, then by field c with field b, etc. I am currently using a bubble sort, but the dataset is starting to get large enough that it is taking too long to execute. To relieve this I decided to switch to a merge sort as I read that it was both more efficient, and a stable sorting algorithm. I got the algorithm working, but it is not sorting stably, so it is only sorted properly by the last search ran on it. Here is the code i currently have, any suggestions would be greatly appreciated: 
sub mergeSort {    #Takes reference to array, index to sort on, beginn
+ing index, and end index
    my ($aref, $index, $begin, $end)=@_;    

    my $size=$end-$begin;            

    if($size<2) {return;}            
    my $half=$begin+int($size/2);        

    mergeSort($aref, $index, $begin, $half);
    mergeSort($aref, $index, $half, $end);    

    for(my $i=$begin; $i<$half; ++$i) {
        if($$aref[$i][$index] > $$aref[$half][$index]) {
            my @va=@$aref[$i];
            my $v=$$aref[$i][$index];
            @$aref[$i]=@$aref[$half];

            my $i=$half;
            while($i<$end-1 && $$aref[$i+1][$index] < $v) {
                (@$aref[$i], @$aref[$i+1])=
                    (@$aref[$i+1], @$aref[$i]);
                ++$i;
            }
            @$aref[$i]=@va;
        }
    }
} # end sub

#Sort by uptime
mergeSort(\@data, 8, 0, scalar(@data));

#Sort by 3rd section of interface cx/x/UX
mergeSort(\@data, 12, 0, scalar(@data));

#Sort by 2nd section of interface cx/X/ux
mergeSort(\@data, 11, 0, scalar(@data));

#Sort by 1st section of interface CX/x/ux
mergeSort(\@data, 11, 0, scalar(@data));

[download]
For clarification, here is my previous sort code: 

sub ASort {

        my ($aref, $index)=@_;
        for ($x=scalar(@$aref);$x>0;$x--){
                for ($j=0;$j<$x-1;$j++){
                        if ($$aref[$j][$index]>$$aref[$j+1][$index]){

                                @temp=@$aref[$j+1];
                                @$aref[$j+1] = @$aref[$j];
                                @$aref[$j] = @temp;
                        }
                }
        }
}


#Sort by uptime
ASort(\@data, 8);

#Sort by 3rd section of interface cx/x/UX
ASort(\@data, 12);

#Sort by 2nd section of interface cx/X/ux
ASort(\@data, 11);

#Sort by 1st section of interface CX/x/ux
ASort(\@data, 11);

[download]

In reply to Need help making my Merge Sort implementation stable by taffer

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.