Merge Sort

Concept:

Divide and conquer:

Let the merge sort recursive function be F. Call F for left half subarray and right half sorted array.

Now merge the two sorted array into one complete sorted array.
Merge takes O(n) and the depth of the recursive tree is Log(n).
Complete complexity: N * Log(n).



def merge_sort(arr):

	_merge_sort(arr, 0, len(arr) - 1)
	return arr 

def _merge_sort(arr, left_index, right_index):

	if left_index < right_index:
		mid_index = (left_index + right_index) / 2

		_merge_sort(arr, left_index, mid_index)
		_merge_sort(arr, mid_index + 1, right_index)

		merge_two_sorted_arrays(arr, left_index, mid_index, mid_index + 1, right_index)

		return arr 


def merge_two_sorted_arrays(arr, left_start_index, left_end_index, right_start_index, right_end_index):

	result = []
	i = left_start_index
	j = right_start_index

	while i < len(left_end_index) and j < len(right_end_index):
		if arr[i] < arr[j]:
			result.append(arr[i])
			i += 1
		else:
			result.append(arr[j])
			j += 1

	result.extend(arr[i:left_end_index + 1])
	result.extend(arr[j:right_end_index + 1])

	arr = result





Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s