inv.c

unsigned int count_inversions(unsigned int *ary, size_t len)
{
    if (len <= 1) {
        printf("base: %u\n", ary[0]);
        return 0;
    }

    size_t i;
    
    size_t l_len = len / 2;
    size_t r_len = len - l_len;
    unsigned int left_inversions = count_inversions(ary, l_len);
    unsigned int right_inversions = count_inversions(ary + l_len, r_len);
    unsigned int count = left_inversions + right_inversions;
    
    // Merge
    unsigned int left[l_len], right[r_len];
    memcpy(left, ary, l_len * sizeof(unsigned int));
    memcpy(right, ary + l_len, r_len * sizeof(unsigned int));
    printf("unmerged: ");
    for (i = 0; i < len; ++i)
        printf("%u ", ary[i]);
    printf("\n");

    
    size_t l = 0, r = 0;
    for (i = 0; i < len; ++i) {
        if (l == l_len) {
            memcpy(ary + i, right + r, r_len - r);
            break;
        } else if (r == r_len) {
            memcpy(ary + i, left + l, l_len - l);
            break;
        }

        if (left[l] <= right[r])
            ary[i] = left[l++];
        else {  
            ary[i] = right[r++];
            count += l_len - l;
        }
    }
    
    printf("merged: ");
    for (i = 0; i < len; ++i)
        printf("%u ", ary[i]);
    printf("\n");

    return count;
}

inv.rb

def count_inversions(ary)
  return {:count => 0, :sorted => ary} if ary.length <= 1

  left = count_inversions ary[0 ... ary.length / 2]
  right = count_inversions ary[ary.length / 2 ... ary.length]
  l_ary = left[:sorted] << Float::INFINITY
  r_ary = right[:sorted] << Float::INFINITY
  l_len = l_ary.length - 1

  l = r = 0
  merged = []
  count = left[:count] + right[:count]

  ary.each do |foo|
    if (l_ary[l] <= r_ary[r])
      merged << l_ary[l]
      l += 1
    else
      merged << r_ary[r]
      r += 1
      count += l_len - l
    end
  end

  {:count => count, :sorted => merged}
end