CODEWITHSUNDEEP
arraysrubyalgorithmrecursionmergesort
Jacob Moore
Jacob Moore

Reputation: 277

Ruby merge sort -- how does this recursive function work?

I'm doing an assignment writing a recursive merge sort algorithm in Ruby. I'm trying to break this down piece by piece in order to be able to wrap my head around it. What I have so far is trying to accomplish the "divide" step until there is only one element left in each array.

a = [5, 2, 4, 6, 1, 7, 3, 8]

def divide(arr)
  return arr if arr.length < 2
    else
      arr1 = puts divide(arr[0..arr.length/2-1])
      arr2 = puts divide(arr[arr.length/2..arr.length])
end

I would think the output would be:

[5] [8]

But it prints out:

5
2

4
6

1
7

3
8

How does it work?

Upvotes: 0

Views: 124

Answers (1)

Danil Speransky
Danil Speransky

Reputation: 30463

You have at least two problems.

First, the else statement has no effect, it's not how you do if else in Ruby.

Second, if a.length < 2 is false then your method will return nil. puts returns nil, x = nil returns nil.

I've added some prints to demonstrate how your code works, I hope it'll help:

$level = 0

def divide(arr)
  return arr if arr.length < 2

  $level += 1

  puts "Working with array #{arr}"

  arr1 = divide(arr[0..arr.length/2-1])
  puts "Level = #{$level} arr1 = #{arr1}"
  arr2 = divide(arr[arr.length/2..arr.length])
  puts "Level = #{$level} arr2 = #{arr2}"

  $level -= 1

  nil
end

divide([5, 2, 4, 6, 1, 7, 3, 8])

The output:

Working with array [5, 2, 4, 6, 1, 7, 3, 8]
Working with array [5, 2, 4, 6]
Working with array [5, 2]
Level = 3 arr1 = [5]
Level = 3 arr2 = [2]
Level = 3 arr1 = 
Working with array [4, 6]
Level = 4 arr1 = [4]
Level = 4 arr2 = [6]
Level = 4 arr2 = 
Level = 4 arr1 = 
Working with array [1, 7, 3, 8]
Working with array [1, 7]
Level = 6 arr1 = [1]
Level = 6 arr2 = [7]
Level = 6 arr1 = 
Working with array [3, 8]
Level = 7 arr1 = [3]
Level = 7 arr2 = [8]
Level = 7 arr2 = 
Level = 7 arr2 =

Upvotes: 3

Related Questions