何度目かのmergesortのお勉強

perl python javascript

今度は同マージソート

Perl

my @b;
sub merge_sort {
    my ($a, $low, $high) = @_;
    $low  //= 0;
    $high //= @$a -1;

    my ($i, $j, $k);
    return if $low >= $high;
    
    my $mid = int( ($low + $high) / 2 );

    merge_sort($a, $low, $mid);
    merge_sort($a, $mid+1, $high);
 
    for ($i = $low; $i <= $mid; $i++) {
        $b[$i] = $a->[$i]; 
    }
 
    for ($i = $mid+1, $j = $high; $i <= $high; $i++, $j--) {
        $b[$i] = $a->[$j];
    }

    $i = $low; $j = $high;
    for ($k = $low; $k <= $high; $k++) {
        if ($b[$i] <= $b[$j]) {
            $a->[$k] = $b[$i++];
        }
        else {
            $a->[$k] = $b[$j--];
        }
    }
}

sub main {
    my @a = (10, 2, 34, 11, 13, 5, 55);
    merge_sort(\@a);
    print join(',', @a), $/;
}

main() unless caller;

Python

b = []
def p(a):
    print ",".join([ str(x) for x in a])

def merge_sort(a, low, high):
    global b
    if len(b) == 0:
        b = [ 0 for i in range(0,len(a)) ]

    if low >= high:
        return

    mid = int( (low+high) / 2 )

    merge_sort(a, low,  mid)
    merge_sort(a, mid+1, high)

    i = low
    while i <= mid:
        b[i] = a[i]
        i += 1

    i = mid + 1
    j = high
    while i <= high:
        b[i] = a[j]
        i += 1
        j -= 1

    i = k = low 
    j = high

    while k <= high:
        if b[i] <= b[j]:
            a[k] = b[i]
            i = i + 1
        else:
            a[k] = b[j]
            j = j - 1
        k = k + 1

def main():
    a = [10, 2, 34, 11, 13, 5, 55, 5];
    merge_sort( a, 0, 7 )
    p(a)

if __name__ == '__main__':
    main()

JavaScript

var b = [];

function merge_sort(a, low, high) {
    if (low >= high) { return }
    
    var mid = Math.floor( (low + high) / 2 );

    merge_sort(a, low, mid);
    merge_sort(a, mid+1, high);

    var i; 
    for (i = low; i <= mid; i++) {
        b[i] = a[i]; 
    }
 
    for (i = mid+1, j = high; i <= high; i++, j--) {
        b[i] = a[j];
    }

    i = low; 
    j = high;
    for (k = low; k <= high; k++) {
        if (b[i] <= b[j]) {
            a[k] = b[i++];
        }
        else {
            a[k] = b[j--];
        }
    }
}

function main() {
    var a = [10, 2, 34, 11, 13, 5, 55];
    merge_sort(a, 0, 6);
    console.log("%s",  a.join(',') );
}

main();

元のコードはCなのだけどPerl,JavaScriptはほぼそのままって感じで書き換えられたけどPythonはちょっと違ったので慣れないのもあって危うくPythonが嫌いになりそうなくらい苦労した。