Implementing Merge Sort algorithm

Question

def merge(arr,l,m,h):
    lis = []
    l1 = arr[l:m]
    l2 = arr[m+1:h]
    while((len(l1) and len(l2)) is not 0):
        if l1[0]<=l2[0]:
            x = l1.pop(0)
        else:
        x = l2.pop(0)
        lis.append(x)
    return lis

def merge_sort(arr,l,h): generating them
    if l<h:
        mid  = (l+h)//2
        merge_sort(arr,l,mid)
        merge_sort(arr,mid+1,h)
        arr = merge(arr,l,mid,h)
    return arr

arr = [9,3,7,5,6,4,8,2]
print(merge_sort(arr,0,7))

Can anyone please enlighten where my approach is going wrong ? I get only [6,4,8] as the answer. I'm trying to understand the algo and implement the logic my own way. Please help.

Debug the small failing example and and compare it with what you expected to happen (even possible with pen and paper). — MrSmith42, Jan 04 '22 at 12:33
Try to explain the variable names to simplify the understanding of your code, please — Franz Kurt, Jan 04 '22 at 12:44
@JaideepSingh Just noticing that the end result with input `[9,3,7,5,6,4,8,2]` is `[6,4,8]` is not enough. Add some `print` statements in the code to print intermediary results. For instance, add `print('sort: ', arr, l, h)` at the beginning of `merge_sort`, and `print('merge: ', arr, l, m, h)` at the beginning of `merge`. — Stef, Jan 04 '22 at 12:45
Oh, by the way, here is an obvious error in the code: `((len(l1) and len(l2)) is not 0)` definitely does not do what you think. Instead, try `(len(l1) > 0) and (len(l2) > 0)` — Stef, Jan 04 '22 at 12:46
Also, `if l1[0]<=l2[0]: x = l1.pop(0) else: x = l2.pop(0)` is wrong for two reasons. (1) The indentation is wrong (I'm surprise you could even execute the code without an immediate syntax error). (2) `l1[0]` inspects the **first** element of the list, but `l1.pop()` pops the **last** element of the list. See https://docs.python.org/3/tutorial/datastructures.html#more-on-lists ; I suggest looking at `l1[-1]` instead of `l1[0]`, that's the last element in the list. — Stef, Jan 04 '22 at 12:49
Oops, somehow I misread, I though you were calling `.pop()`, not `.pop(0)`. I'd still recommend dealing with the "end" of the list rather than the "beginning" of the list, since popping from the beginning is a very costly operation (when an element is popped, every element after it is "shifted" towards the beginning to fill the gap; if you pop the first element, the whole list is rewritten). — Stef, Jan 04 '22 at 12:56
@Stef "is not" caused "allocating too much memory" error. Why would that happen ? By the way I've got it sorted, thanks to all of yours help. — Jaideep Singh, Jan 04 '22 at 13:17
@JaideepSingh `((len(l1) and len(l2)) is not 0)` does not mean "len(l1) and len(l2) are two numbers different from 0". Logical operators `and`, `or`, `is`, `is not` should be seen as just that: logical operators. They are parsed and behave the same way as arithmetic operators. [...] — Stef, Jan 04 '22 at 13:21
[...] When you write `((len(l1) and len(l2)) is not 0)`, the parentheses mean that `(len(l1) and len(l2)` will be evaluated first. Call `v` the resulting value. Then, the whole expression will evaluate to `v is not 0`. Since `len(l1)` and `len(l2)` are numbers, but `and` expects truth-values, the numbers are "converted" to truth-values first, with the following rule: nonzero numbers are True, 0 is False. So, `len(l1) and len(l2)` will be `True` if both lengths are nonzero, and `False` if at least one length is zero. (...) — Stef, Jan 04 '22 at 13:23
(...) then you use the result, True or False, in `... is not 0`. So basically this is going to be `True is not 0` or `False is not 0`. Both those statements are True, so the overall condition is always true. Thus the while-loop is an infinite loop. — Stef, Jan 04 '22 at 13:24
@JaideepSingh See also these two questions on that issue: [Why does "a == x or y or z" always evaluate to True?](https://stackoverflow.com/questions/20002503/why-does-a-x-or-y-or-z-always-evaluate-to-true) and [How to test multiple variables for equality against a single value?](https://stackoverflow.com/questions/15112125/how-to-test-multiple-variables-for-equality-against-a-single-value) — Stef, Jan 04 '22 at 13:26
So the condition could be rewritten in any of these ways: `0 not in {len(l1), len(l2)}` (which works, but is a bit unusual); or `len(l1) != 0 and len(l2) != 0` or `len(l1) > 0 and len(l2) > 0`; or `len(l1) and len(l2)` (which works because a number is converted to True if nonzero, to False if 0) or even `l1 and l2` (which works because a list is converted to True if non-empty, to False if empty). — Stef, Jan 04 '22 at 13:33
You could also use the `all` or `any` functions, especially if you had many lists: `all(len(l) > 0 for l in (l1, l2, l3, l4))` or `not any(len(l) == 0 for l in (l1, l2, l3, l4))` or directly `all((l1,l2,l3,l4))` — Stef, Jan 04 '22 at 13:34

trincot · Accepted Answer · 2022-01-04T13:28:27.883

Several issues:

As you consider h to be the last index of the sublist, then realise that when slicing a list, the second index is the one following the intended range. So change this:

Wrong Right

l1 = arr[l:m] l1 = arr[l:m+1]

l2 = arr[m+1:h] l2 = arr[m+1:h+1]
As merge returns the result for a sub list, you should not assign it to arr. arr is supposed to be the total list, so you should only replace a part of it:
```
arr[l:h+1] = merge(arr,l,mid,h)
```
As the while loop requires that both lists are not empty, you should still consider the case where after the loop one of the lists is still not empty: its elements should be added to the merged result. So replace the return statement to this:
```
return lis + l1 + l2
```
It is not advised to compare integers with is or is not, which you do in the while condition. In fact that condition can be simplified to this:
```
while l1 and l2:
```

With these changes (and correct indentation) it will work.

Further remarks:

This implementation is not efficient. pop(0) has a O(n) time complexity. Use indexes that you update during the loop, instead of really extracting the values out the lists.

It is more pythonic to let h and m be the indices after the range that they close, instead of them being the indices of the last elements within the range they close. So if you go that way, then some of the above points will be resolved differently.

Corrected implementation

Here is your code adapted using all of the above remarks:

def merge(arr, l, m, h):
    lis = []
    i = l
    j = m
    while i < m and j < h:
        if arr[i] <= arr[j]:
            x = arr[i]
            i += 1
        else:
            x = arr[j]
            j += 1
        lis.append(x)
    return lis + arr[i:m] + arr[j:h]

def merge_sort(arr, l, h):
    if l < h - 1:
        mid  = (l + h) // 2
        merge_sort(arr, l, mid)
        merge_sort(arr, mid, h)
        arr[l:h] = merge(arr, l, mid, h)
    return arr


arr = [9, 3, 7, 5, 6, 4, 8, 2]
print(merge_sort(arr,0,len(arr)))

Wrong	Right
`l1 = arr[l:m]`	`l1 = arr[l:m+1]`
`l2 = arr[m+1:h]`	`l2 = arr[m+1:h+1]`

Implementing Merge Sort algorithm

1 Answers1

Further remarks:

Corrected implementation