マージソート（C言語、Go言語）

マージソートを C と Go で実装してみました。このソートは二つの配列をマージ（統合）する作業がキモです。それぞれソートされた二つの配列を、統合してひとつのソートされた配列を作るわけですね。これができればあとは簡単です。

C言語。
merge_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void merge(int ar[], int p, int q, int r) {
    int n1, n2, i, j, k;
    int *left, *right;
    
    n1 = q - p + 1;
    n2 = r - q;
    
    left  = malloc(sizeof(int) * (n1 + 1));
    right = malloc(sizeof(int) * (n2 + 1));
    
    for (i = 0; i < n1; i++) left[i]  = ar[p + i];
    for (i = 0; i < n2; i++) right[i] = ar[q + i + 1];
    
    left[n1]  = (int)INFINITY;
    right[n2] = (int)INFINITY;
    
    i = j = 0;
    for (k = p; k <= r; k++) {
        if (left[i] < right[j]) {
            ar[k] = left[i++];
        } else {
            ar[k] = right[j++];
        }
    }
    
    free(right);
    free(left);
}

void merge_sort(int ar[], int p, int r) {
    if (p >= r) return;
    int q = (p + r) / 2;
    merge_sort(ar, p, q);
    merge_sort(ar, q + 1, r);
    merge(ar, p, q, r);
}

int main() {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    merge_sort(ar, 0, len - 1);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

　
Go言語。C言語と同じように考えていましたが、C の配列と Go のスライスはかなりちがうので、勘ちがいで苦しみました。最初から考え直してみてやっとできました。実際、C と全然ちがいますよね。
merge_sort.go

package main
import "fmt"

func merge(left, right []int) []int {
    result := []int{}
    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }
    return append(result, append(left, right...)...)
}

func merge_sort(ar []int) []int {
    if len(ar) > 1 {
        q := len(ar) / 2
        ar = merge(merge_sort(ar[:q]), merge_sort(ar[q:]))
    }
    return ar
}

func main() {
    ar := merge_sort([]int{3, 1, 5, 10, 2, 9, 7, 0})
    fmt.Println(ar)
}

　
C は return で配列が返せないけれど、Go はスライスを返せるというちがい…。

Ruby 版。

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0] <= b[0]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    return self if length <= 1
    q = length / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end