Merge Sort

Merge Sort script performs a merge sort with a float- double-typed value at the first column of the line. It was originally designed to fill the gap in the sort command in UNIX environment.

It reads the first column of each line and evaluates it for sorting. Therefore, the lines as following:

9.0588954931254e-06 AAA
0.000155112355326217 BBB
3.47920132209527e-05 CCC
2.58067634638665e-05 DDD
0.00273331742528102 EEE

is converted as following.

9.0588954931254e-06 AAA
2.58067634638665e-05 DDD
3.47920132209527e-05 CCC
0.000155112355326217 BBB
0.00273331742528102 EEE

Usage : merge_sort.pl < Input_File

#!/usr/bin/perl

#    merge_sort.pl
#          
#    Copyright(C) Since 2006 Akira KAKINOHANA All Rights Reserved
#    Author :  Akira KAKINOHANA <kira@kirameister.net>
#    Distributed at : http://softwares.kirameister.net/
#    
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation version 3.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    For GNU General Public License, see <http://www.gnu.org/licenses/>.

my @table;
my $N = 0;
while(){
    chomp;
    $table[$N] = $_;
    $N++;
  }
&sort(\@table);

foreach $k (@table){
    print "$k\n";
  }

sub sort {
    (my $a) = @_;
    my $num = @$a;
    my $ref = \@a;
    &mergeSort($a);
  }

sub mergeSort {
    (my $a) = @_;

    return if (@$a <= 1);

    my $m = int( @$a / 2 );
    my $n = @$a - $m;

    my @a1;
    my @a2;
    for (my $i=0;$i<$m;$i++){$a1[$i] = $$a[$i]}
    for (my $i=0;$i<$n;$i++){$a2[$i] = $$a[$m+$i]}
    &mergeSort(\@a1);
    &mergeSort(\@a2);
    &merge(\@a1, \@a2, $a);
  }

sub merge {
    ($a1, $a2, $a) = @_;
    $i = 0;
    $j = 0;

    while ($i < @$a1 || $j < @$a2) {
        ($cola1) = split( / /, $$a1[$i]);
        ($cola2) = split( / /, $$a2[$j]);
        if ($j >= @$a2 || ($i<@$a1 && $cola1 < $cola2) ) {
            $$a[$i+$j] = $$a1[$i];
            $i++;
	  }else{
            $$a[$i+$j] = $$a2[$j];
            $j++;
	  }
      }
  }

download

merge_sort.pl