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: You are ordering strings: `'9989' < '999' < '9990'`. If you want to order
integers, you'll have to convert your input list to integers.

