Merge Sort written in python.

mergesort.py

def merge_lists(left_sublist,right_sublist):
	i,j = 0,0
	result = []
	#iterate through both left and right sublist
	while i<len(left_sublist) and j<len(right_sublist):
		#if left value is lower than right then append it to the result
		if left_sublist[i] <= right_sublist[j]:
			result.append(left_sublist[i])
			i += 1
		else:
			#if right value is lower than left then append it to the result
			result.append(right_sublist[j])
			j += 1
	#concatenate the rest of the left and right sublists
	result += left_sublist[i:]
	result += right_sublist[j:]
	#return the result
	return result

def merge_sort(input_list):
	#if list contains only 1 element return it
	if len(input_list) <= 1:
		return input_list
	else:
		#split the lists into two sublists and recursively split sublists
		midpoint = int(len(input_list)/2)
		left_sublist = merge_sort(input_list[:midpoint])
		right_sublist = merge_sort(input_list[midpoint:])
		#return the merged list using the merge_list function above
		return merge_lists(left_sublist,right_sublist)


#test run
number_list = [3,1,5,3,2,5,8,2,9,6,12,53,75,22,83,123,12123]
print merge_sort(number_list)

Hi! I am a little new to programming, can someone please explain to me
#concatenate the rest of the left and right sublists result += left_sublist[i:] result += right_sublist[j:] #return the result return result
I didn't quite understand it.
Thanks.

Hi! I am a little new to programming, can someone please explain to me
#concatenate the rest of the left and right sublists result += left_sublist[i:] result += right_sublist[j:] #return the result return result
I didn't quite understand it.
Thanks.

HI hadizorkot331,

I’m not the one who wrote the code, but I’ll try to explain it.
It’s best to watch an overview video on YouTube first
And then run the code line-by-line, as if you were a computer, and just write down on paper what’s happening.

No shame in coding on paper or writing things out. I do it myself.

The first couples of lines we define several functions (which start with “def” in Python)

At line 34, we have an undordered list of nums called “number_list”.
Line 35, we call the “merge_sort” function on this “number_list”, and feed number_list into that function

This brings us to line 20 (def merge_sort(input_list))
If the length of that list we inputed (here, the number_list) is 0 or 1 characters long, it’s already sorted, so in line 23, we return it
This is super important because this is the base case and prevents our code from running forever

But if we’re not so lucky, in line 24, what we do is we’re going to have to split the list in half and then call merge_sort() recursively on the LEFT and RIGHT half of the number list

Line 26: set the midpoint to be the length of the inputted number list, divided by 2.
The int() in line 26 casts it into an integer, which is a number that’s NOT a fraction (i.e., it’s a whole number like 1, 2, 3, 4…)
Note that the midpoint here refers to the visual middle of the list. It is NOT the mean or median number (average), it’s the actual middle of the list, as it is right now (unsorted)

Line 27: Call merge_sort() on the left half of the list
The syntax [:midpoint] means to take the input_list from the first number up to the midpoint (which we calculated in line 26)

Line 28: The syntax [midpoint:] means to take the input_list from the midpoint index up to the last number in the liast

The code then goes on to do merge_sort on the left and right halves of the list

If you get confused here, try it for yourself—
Run midpoint = int(len(input_list)/2) and find the midpoint of the number list.

When it’s done, we hit
Line 30: where we call the merge_lists() function on the left and right sublists (left and right halves of the number list)

Basically, we go through the merge_sort() function over and over again, splitting the list into smaller and smaller left and right halves

So here, we have
[3,1,5,3,2,5,8,2,9,6,12,53,75,22,83,123,12123]

The length here is 17, so the midpoint is around 8.5, but because we did int(), it rounds it to a whole integer

We run merge_sort() on the left half, or the first 8 numbers.
Then we run merge_sort() on the right half, or the 9th through 17 numbers

Then within that, we split it further to
Left: run mergesort on indices 0 through 4, then 5 through 8
Right: run mergesort on indices 9 through 13, then 14 through 17
Etc.

Recursion is just running a function on itself.
We eventually hit a case where the length of the input list is <= 1, so it never runs forever

Once that’s done, everything is sorted, we merge the left and right halves

This takes us to line 1, def_mergelists(), which takes in the left and right sublists, which are INDIVIDUALLY sorted, but not in order if you put them together (yet)

Start a counter at i = 0 and j = 0
Then make an empty list called “empty”

We are going to use the “I” as a counter for the left sublist
And “j” as a counter for the right sublist
And as we go through each of the sublists, one number at a time, we will update the “empty” list with values from the left and right sublist. In the correct order

So say left sublist is [1, 3, 7, 8], and the right sublist is [1, 5, 9, 11]

Left sublist at index 0 is “1”, and right sublist at index “0” is also “1”
So we append sublist[0] to the empty result list
Result list is now [1]
And I is increased to index 1

Now left sublist at index 1 is “3”, and right sublist at index 0 is “1”
1 < 3
So we append the smaller number to result list
Result list is now [1, 1]
And j is increased to index 1

Now left sublist at index 1 is “3” and right sublist at index 1 is “4”
3 < 5
So we append the 3 to results
Results is now [1, 1, 3]
And “I” is increase to index 2

Etc.

Because of the while loop on line 5, we only do this up until we still have items left in left and right sublist

Once either list runs out, we jump down to line 15
Because EITHER or BOTH the left and right sublist are now empty, then it stands that either the left OR the right OR neither sublist still has items
And since the individual sublists for left and right are already sorted, we just gotta add the remaining numbers to results

Finally, we return “result”