1

I have some code further below which is doing a merge sort. It was implemented using a python Array of ints (list of ints) as my initial test case. This went well. However, once this was working, I generated a random set of numbers to test further. This list is a numpy array. The merge sort does not work with the numpy array, the results look like repeated figures and like the reconstruction isn't working as intended.

My assumption is that the way the subdivided array is passed to mergesort and then recombined in memory is different between the two, and that is what is causing the issue. However, I am not certain.

Any thoughts?

example arrays: working with:

Array = [48,44,19,59,72,80,42,65,82,8,95,68]

not working with

unsorted = np.random.randint(1, 1000, 150)

The merge sort code:

#function for merging two sub-arrays
def merge(left, right, Array):
    i = 0
    j = 0
    k = 0

    while (i < len(left) and j < len(right)):
        if (left[i] < right[j]):
            Array[k] = left[i]
            i = i+1
        else:
            Array[k] = right[j]
            j = j+1

        k = k+1

    while (i < len(left)):
        Array[k] = left[i]
        i = i+1
        k = k+1

    while (j < len(right)):
        Array[k] = right[j]
        j = j+1
        k = k+1
 
#function for dividing and calling merge function
def mergesort(Array):
    n = len(Array)
    if (n < 2):
        return

    mid = n / 2
    
    left = Array[0 : int(np.round(mid))]
    right  = Array[int(np.round(mid)) : n]
    print("array size = {}, leftsize= {}, rightsize= {}".format(n, len(left), len(right)))

    mergesort(left)
    mergesort(right)

    merge(left, right, Array)
    
    return Array

Then just need to call the following to compare the output:

mergesort(Array)
mergesort(unsorted)
6
  • Have you tried with mid = n // 2 i/o int(np.round(mid))? Commented Oct 30, 2020 at 13:18
  • Interestingly your unsorted is an array while Array is a list. Commented Oct 30, 2020 at 13:20
  • Hi, This is a good workaround for the rounding, but results are still the same unfortunately. Commented Oct 30, 2020 at 13:21
  • @KlausD. Yep, Python array is just a list, right? But fundamentally, I'm not sure why they are producing such different results. Being that one works and the other doesnt't. Commented Oct 30, 2020 at 13:22
  • No, a list is not just an name for an array. The only things they have in common is that they use the [ ] syntax and that they are an ordered collection of items. Commented Oct 30, 2020 at 13:28

1 Answer 1

1

Add left = left.copy() at the start of merge, otherwise it's a view of Array so that writing into Array overwrites left.

(right is also a view, but that's ok since you're not overwriting it faster than you're reading it)

Sign up to request clarification or add additional context in comments.

1 Comment

@Didier: Welcome to a confusing world: slices of python lists (which are implemented as vectors and use the Array syntax of other languages) duplicate the data whereas slices of numpy arrays, which use the same syntax are just views of said objects, sharing the data.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.