Cormen problem 2.4c - insertion sort wrt number of inversions

insertionsort.jl

julia> function insertionsort_ex(A::Array{T}) where T <: Number
           for i in 1:length(A)-1
               value = A[i+1] 
               j = i
               while value < A[j] && 1 < j # each iteration eliminates one inversion
                   A[j+1] = A[j] # running time depends on number of inversions to eliminate, θ(n+d)         
                   j -= 1        # where n = length(A)-1 and d = number of inversions
               end
               A[j+1] = value
           end
           return A
       end
insertionsort_ex (generic function with 1 method)

julia> x = randn(5)
5-element Array{Float64,1}:
  0.71922
  1.21506
  1.00055
 -1.20689
 -2.00336
                      
julia> @time insertionsort_ex(x)
  0.000006 seconds (83 allocations: 6.092 KiB)
5-element Array{Float64,1}:
 -2.00336
 -1.20689
  0.71922
  1.00055
  1.21506

julia>