Skip to content

Instantly share code, notes, and snippets.

@chbatey
Created July 11, 2013 20:03
Show Gist options
  • Save chbatey/5978720 to your computer and use it in GitHub Desktop.
Save chbatey/5978720 to your computer and use it in GitHub Desktop.
Merge sort in python
class MergeSort(object):
@staticmethod
def sort(array):
if len(array) <= 1:
return array
else:
middle = len(array)/2
left_half = MergeSort.sort(array[:middle])
right_half = MergeSort.sort(array[middle:])
merged = []
i,j,= 0,0
while (i + j) < (len(left_half) + len(right_half)):
if i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
merged.append(left_half[i])
i += 1
else:
merged.append(right_half[j])
j += 1
elif i < len(left_half):
merged.append(left_half[i])
i += 1
elif j < len(right_half):
merged.append(right_half[j])
j += 1
return merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment