https://codility.com/programmers/lessons/14/

array_inversion_count.rb

# First sort the input using an nlogn method
# Then iterate over the array, finding the index of each value in the sorted array
# The index of the value in the sorted array is the inversion count, because all items to the left are less
# Sum those up
# Be sure to use the most efficient searching and not build in. (nlogn sort and logn search)
def solution(a)
    return 0 if a.empty?
    sorted = a.sort
    
    inversions = a.each_with_index.map do |val, index|
        index_in_sorted = bin_search(sorted, val)
        sorted.delete_at(index_in_sorted)
        index_in_sorted
    end.reduce(&:+)
    
    inversions > 1_000_000_000 ? -1 : inversions
end

def bin_search(arr, val)
    bin_search_r(arr, val, 0, arr.count - 1)
end

def bin_search_r(arr, val, min, max)
    mid = (max+min)/2
    
    if arr[mid] > val
        bin_search_r(arr, val, min, mid - 1)
    elsif arr[mid] < val
        bin_search_r(arr, val, mid + 1, max)
    else
        found_index = mid
        while(found_index > 0 && arr[found_index-1] == val)
            found_index -= 1
        end
        found_index
    end
end

First version here misses performance because it's n*2, but I loved the simplicity that Ruby allows!

Second version is much more complex, but solves it in the space required. If this was going to be done on arrays < 10000, I would definitely opt for the first one.

Ruby 2.3 introduces Array#bsearch_index which would remove most of this code

Credit to https://www.quora.com/How-can-the-number-of-inversions-between-two-arrays-be-calculated-in-O-N-log-N because I wouldn't have known that about inversion count.