Merge Sort removing items from array rather than using indexes

Python Help
1

I was looking at a few descriptions of how a merge sort worked and it struck me that rather than using a var for an index when merging 2 lists you could just remove the value you were adding to the new list and just compare the first 2 values in each list in the next pass.

I ask this partly to see if I properly understood how it works but also wondered if I do this if it affects performance. Even if it does I think it creates code that is a little easier to understand.

Thoughts?

2

There are probably dozens of different ways to implement a merge sort, which will differ slightly in performance.

Without looking at actual code, it is impossible to say whether your understanding is correct, and whether or not your proposed change will work. But my guess is that removing items one at a time from the lists being merged will probably slow things down rather than speed them up. But what do I know?

If you want to explore this question further, there is no substitute for writing two merge sort functions, one with the index and one using your deletion trick, and see if:

  1. they behave the same;
  2. they behave correctly;
  3. how they perform.
3

You absolutely CAN do it that way. When I was teaching data structures and algorithms, what I’d usually do would be to have a pair of arrays and a pair of counters that would advance through them, denoting the “start” of each array (more efficient than actually removing the elements). The core merge loop looks something like this:

def merge(arr1, arr2):
    d1 = d2 = 0
    merged = []
    while d1 < len(arr1) and d2 < len(arr2):
        if arr2[d2] < arr1[d1]:
            merged.append(arr2[d2])
            d2 += 1
        else:
            merged.append(arr1[d1])
            d1 += 1
    return merged + arr1[d1:] + arr2[d2:]

(Coded from memory, may contain bugs.) At any time, arr1[d1:] and arr2[d2:] are your two arrays of items awaiting merging. In theory you could write it like this, which would be functionally equivalent but slower:

def merge(arr1, arr2):
    merged = []
    while arr1 and arr2:
        if arr2[0] < arr1[0]:
            merged.append(arr2.pop(0))
        else:
            merged.append(arr1.pop(0))
    return merged + arr1 + arr2

In this version, arr1 and arr2 are the two collections of unmerged values. Try both out, add a bunch of print calls, and you should be able to see the equivalence.

Sometimes, in computer programming, it’s actually worth thinking of an “array” as only being part of an array (especially, for instance, with an in-place quicksort, where there are two arrays in one); it takes some getting your head around, but it’s functionally equivalent to actually breaking things out, and a lot faster to run.

4

Two things to say:

  1. Popping from the beginning of a list is slow - O(n). If you do that for each element, that’s O(n^2) - albeit with a decent constant.
  2. Popping from the beginning of a deque is fast. So maybe put your values in a pair of deques instead.
5

This is very true; but let’s be honest here, ANY manual implementation of a sorting algorithm isn’t going to be particularly fast. The purpose is usually to exemplify the algorithm, not to actually be faster than calling stuff.sort() :slight_smile: Though what you say here could be a segue into a completely orthogonal (and equally valuable) discussion of data structures designed for dual-ended manipulation.

6

Yeah.