Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
merge sort
#1
This one always blows my mind

def merge(left, right):
    combined, left_index, right_index = [], 0, 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            combined.append(left[left_index])
            left_index += 1
            continue
        combined.append(right[right_index])
        right_index += 1
    combined += left[left_index:] + right[right_index:]
    return combined


def merge_sort(current):
    if len(current) < 2:
        return current

    m = int(len(current)/2)
    return merge(merge_sort(current[:m]), merge_sort(current[m:]))


if __name__ == '__main__':
    print(merge_sort([8, 6, 3, 0, 4, 5, 3, 9, 2]))
Reply
#2
What about this one?
from heapq import merge

def merge_sort(current):
    if len(current) < 2:
        return current
 
    m = int(len(current)/2)
    return merge(merge_sort(current[:m]), merge_sort(current[m:]))
 
 
if __name__ == '__main__':
    print(list(merge_sort([8, 6, 3, 0, 4, 5, 3, 9, 2])))
Output:
[0, 2, 3, 3, 4, 5, 6, 8, 9]
Reply
#3
Just being smart-ass Smile

I like floor division more than division and converting to int:

>>> int(3/2)
1
>>> 3//2
1
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#4
Hmmm investigating heapq

EDIT: Yup Gribouillis you always know all the good modules hahaha
Reply
#5
rootVIII Wrote:EDIT: Yup Gribouillis you always know all the good modules hahaha
In fact the same thing happened to me a long time ago. I wrote a clever merge() function in a forum and then I discovered that the standard library has a merge() function since version 2.6. That's how one learns the libraries the hard way!
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020