life is short - you need Python!

Today I post the python implementation of merge sort. This is straight-forward implementation of the algorithm presented in the book Introduction to Algorithms [CLRS]. If you think the implementation can be more Pythonic, feel free to comment. Here is my code: def merge(li, start, mid, end): left_li = [] left_li.extend(li[start : mid+1]) right_li = [] right_li.extend(li[mid+1: end+1]) left_li.append(2147483647) right_li.append(2147483647) i = 0 j = 0 for k in range(start, end+1): if left_li[i] <= right_li[j]: li[k] = left_li[i] i += 1 else: li[k] = right_li[j] j += 1 def merge_sort(li, start, end): if start < end: mid = (start + end) / 2 merge_sort(li, start, mid) merge_sort(li, mid+1, end) merge(li, start, mid, end) if __name__ == "__main__": li = [5, 2, 4, 7, 1, 3, 2, 6, -4] print li merge_sort(li, 0, len(li)-1) print li You can test the merge sort implementation against this problem:

In my previous post, I showed the iterative way to implement binary search algorithm in Python. Here comes the recursive way. def binary_search_recursive(li, left, right, key): while True: if left > right: return -1 mid = (left + right) / 2 if li[mid] == key: return mid if li[mid] > key: right = mid - 1 else: left = mid + 1 return binary_search_recursive(li, left, right, key) if __name__ == "__main__": li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12] left = 0 right = len(li) for key in [8, 6, 1, 12, 7]: index = binary_search_recursive(li, left, right, key) print key, index

Today I am going to post the code for binary search. This one is iterative and the next one will be recursive. If you don't know about binary search, please read the wikipedia article first. Now, here is my Python implementation of binary search algorithm: def binary_search_iterative(li, left, right, key): while True: if left > right: return -1 mid = (left + right) / 2 if li[mid] == key: return mid if li[mid] > key: right = mid - 1 else: left = mid + 1 if __name__ == "__main__": li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12] left = 0 right = len(li) for key in [8, 6, 1, 12, 7]: index = binary_search_iterative(li, left, right, key) print key, index

I am working on my Python coding skills and this time reviewing various algorithms with which I have not been in touch for many days. So I start with sorting, here is my code for insertion sort: def insertion_sort(ara): for j in range(1, len(ara)): key = ara[j] i = j - 1 while i >= 0 and key < ara[i]: ara[i+1] = ara[i] i -= 1 ara[i+1] = key return ara if __name__ == "__main__": ara = [10, 5, 2, 9, 4, 8, 9, 2, 1] print insertion_sort(ara) More python implementation of various algorithms are coming soon. Meanwhile if you feel that there is chance to improve my code, or make it more pythonic, please feel free to comment. Oh, if you are not familiar with algorithms yet and wording what the ... is insertion sort, please visit the wikipedia article on insertion sort .