Python: Merge sort

Question

How can I improve this code?

#import sys
#sys.setrecursionlimit(1500)

def get_input():
    input_str = input("Enter elements to be sorted: ")
    try:
        lst = list(map(int, input_str.split()))
    except:
        raise TypeError("Please enter a list of integers only, seperated by a space!!")
    return lst

def merge(thelist, start_idx, mid_idx, last_idx):
    size_left = mid_idx - start_idx + 1
    size_right = last_idx - mid_idx

    left_lst = []
    right_lst = []

    for i in range(size_left):
        left_lst.append(thelist[start_idx + i])

    for j in range(size_right):
        right_lst.append(thelist[mid_idx + 1 + j])

    left_idx = 0
    right_idx = 0
    curr_idx = start_idx

    while left_idx < size_left and right_idx < size_right:
        if left_lst[left_idx] <= right_lst[right_idx]:
            thelist[curr_idx] = left_lst[left_idx]
            left_idx += 1

        else:
            thelist[curr_idx] = right_lst[right_idx]
            right_idx += 1

        curr_idx += 1

    while left_idx < size_left:
        thelist[curr_idx] = left_lst[left_idx]
        curr_idx += 1
        left_idx += 1

    while right_idx < size_right:
        thelist[curr_idx] = right_lst[right_idx]
        curr_idx += 1
        right_idx += 1

def merge_sort(thelist, start_idx, last_idx):
    if len(thelist) == 0:
        print("Empty list!!")

    elif len(thelist) == 1:
        print("Only one element!!")

    elif start_idx < last_idx:
        mid_idx = int((start_idx + last_idx) / 2)
        merge_sort(thelist, start_idx, mid_idx)
        merge_sort(thelist, mid_idx + 1, last_idx)
        merge(thelist, start_idx, mid_idx, last_idx)

if __name__ == '__main__':
    input_list = get_input()
    merge_sort(input_list, 0, len(input_list) - 1)
    print(*input_list, sep = ", ")

greybeard · Accepted Answer · 2019-06-30 05:46:08Z

You can adhere to the Style Guide for Python Code (Python Enhancement Proposal (PEP) 8) (there is tool support for this):

Comment your code properly.
Document your code properly.
In the code, using docstrings, making the documentation accessible to IDEs and introspection.

The first thing to document would be the interface of merge_sort():
it may be of interest that it does not return something useful, but modifies thelist.
I think start_idx and last_idx should have default values. While I don't see how to specify something like last_idx=len(thelist) correctly, Python uses index -1 for last element - you'd need to document last_idx to be inclusive (as the name suggests, anyway). (Python commonly uses right index exclusive.) An alternative would be to use None for to the end.
Better get rid of printing in a function of general use than document it does so for specific input.

Having merge() work in-place, too, causes avoidable "copies" - allocate one buffer in ("top-level") merge_sort and "merge to and fro'".

Python has a built-in for selecting a range of items in a sequence object: slicing - do not use loops for this.

You can denote int(x / 2) as (x // 2).

(I'm reluctant to present code as there are too many things I've seen done more to my liking or would to much differently myself.) — greybeard
– greybeard, Commented Jun 30, 2019 at 5:58

Stack Exchange Network

Python: Merge sort

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Python: Merge sort

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions