Merge Sort on Python: Unusual pattern of result obtained

Question

I have a unsorted array of 10,000 integers from 0 to 9,999. I wanted to apply merge sort on this unsorted array and I wrote the following code-

import sys
def merge_sort(data):
    result = []
    if len(data) <= 1:
        return data
    else:
        mid = int(len(data)/2)
        left = data[:mid]
        right = data[mid:]
        sorted_left = merge_sort(left)
        sorted_right = merge_sort(right)
        i = j = k = 0
        total_len = len(sorted_left) + len(sorted_right)
        for k in range(0, total_len):
            if i < len(sorted_left) and j < len(sorted_right):
                if sorted_left[i] < sorted_right[j]:
                    result.append(sorted_left[i])
                    i = i+1
                    k = k+1
                elif sorted_left[i] > sorted_right[j]:
                    result.append(sorted_right[j])
                    j = j+1
                    k = k+1
            elif i < len(sorted_left):
                result.append(sorted_left[i])
                i = i+1
                k = k+1
            elif j < len(sorted_right):
                result.append(sorted_right[j])
                j = j+1
                k = k+1
            else:
                sys.exit("There is some issue with the code")
        return result
print merge_sort(data)

So when I sort this data, I get a correct sort order except for a few entries. For example- towards the end I get this kind of result-

[...'9989', '999', '9990', '9991', '9992', '9993', '9994', '9995', '9996', '9997', '9998', '9999']

As you might observe, number '999' is at the wrong place. Not just in this snippet but it happens in other places too like '995' appearing between '9949' and '9950'.So anybody has any idea why this is happening? P.S.- I ran this code for debug and it ran without errors producing these results

Answer 1

Your data is in strings, not numbers. To convert to integers, use:

data = [int(x) for x in data]

Python will "compare" a wide variety of objects. For example:

>>> "a" < "ab"
True
>>> None < "a"
True
>>> 1 < "a"
True

If you compare such items, python will not object.

Comparison in python

For integers and strings, python has built-in methods for comparisons. For objects that you create, you can define your own comparison methods. Methods that you can define for your objects that python will use for comparison include:

object.__lt__(self, other)
object.__le__(self, other)
object.__eq__(self, other)
object.__ne__(self, other)
object.__gt__(self, other)
object.__ge__(self, other)

By defining your own methods for your objects, there is great flexibility.