educative.io

Educative

Implement Merge Sort inputs, outputs, criteria unclear

It’s unclear how function mergeSort is supported to operate, and what it returns. (Or if educative tracks some mutation or number of moves to measure “success”, as with Towers of Hanoi).

i looked at Java and saw void type for merge sort. So - how does a function recurse if there is no return data? (And no global structure).

A common approach is to make new sub-arrays, with array.splice(), like this:
https://dev.to/mcfrank16/understanding-merge-sort-in-javascript-4cne
Though space-intensive, the algorithm is very clear, and there is no need to pass around ints p, r, or q.

The description here makes it sound as if you are not actually dividing, just specifying smaller sub-arrays of the original structure.
https://www.educative.io/courses/visual-introduction-to-algorithms/jB0Yz
I understand wanting to reduce space complexity, but the problem description needs to specify inputs, outputs, and success criteria.

1 Like

I’m confused. I thought it would work like this but I think I’m messing up the passing around of the full array with returning subarrays.

def mergeSort(array, p, r):

  if p>=r:
return

  if p==r:
return 

  q = (p + r) // 2
  array1 = mergeSort(array, p, q)
  array2 = mergeSort(array, q+1, r)
  return merge(array, p, q, r)