Implementation of insertion sort in Ruby, code correctness

Question

To implement an insertion sort that sorts an array with optional block to determine sorting order, how can I improve this code? (Seeking best practices and code correctness)

def custom_insertion_sort(arr)
 for i in (1..arr.length-1)
 curr = arr[i]
 compare = i-1
 if block_given?
 sorted = yield arr, compare, curr
 else
 sorted = arr[compare] < curr
 end
 while compare >= 0 && sorted
 arr[compare+1] = arr[compare]
 compare -= 1
 if block_given?
 sorted = yield arr, compare, curr
 else
 sorted = arr[compare] < curr
 end
 end
 arr[compare+1] = curr
 end
 arr
end

Answer 1

1. Your block usage yield arr, compare, curr is rather weird:

   custom_insertion_sort(array){ |_, i, j| _[i].abs > j.abs }
   

   I would do yield arr[compare], curr:

   naki_insert_sort(array){ |i, j| i.abs > j.abs }
   

2. You may use ...n syntax instead of ..n-1

3. You are sorting inplace, operating with an array like with a memory pointer, so you don't have to return arr from the function.

4. Instead of writing comparision code twice you can either define lambda or put it just inside while condition.

And after a bit more golf I've got this:

def naki_insert_sort arr
 for i in (1...arr.length)
 curr = arr[compare = i]
 while 0 <= (compare -= 1) && ( block_given? ?
 yield(arr[compare], curr) :
 arr[compare] < curr
 )
 arr[compare + 1] = arr[compare]
 end
 arr[compare + 1] = curr
 end
end

But looks like Insertion sort and Ruby don't actually suit each other, because using indexes isn't functional.

• tokland: "You are sorting inplace, operating with an array like with a memory pointer, so you don't have to return arr.". Indeed, but core Ruby methods tend to do this (on the other hand Python does not, to emphasise that they are in-place operations).