| 1 | class MergeSort(object): |
| 2 | def __init__(self, numbers): |
| 3 | self.values = numbers |
| 4 | self.count = len(numbers) |
| 5 | |
| 6 | def sort(self): |
| 7 | self.merge_sort(0, self.count - 1) |
| 8 | return self.values |
| 9 | |
| 10 | def merge_sort(self, low, high): |
| 11 | if low < high: |
| 12 | mid = (low + high) // 2 |
| 13 | |
| 14 | self.merge_sort(low, mid) |
| 15 | self.merge_sort(mid + 1, high) |
| 16 | self.merge(low, mid, high) |
| 17 | |
| 18 | def merge(self, low, mid, high): |
| 19 | b = [] |
| 20 | i = low |
| 21 | j = mid + 1 |
| 22 | |
| 23 | while i <= mid and j <= high: |
| 24 | if self.values[i] <= self.values[j]: |
| 25 | b.append(self.values[i]) |
| 26 | i += 1 |
| 27 | else: |
| 28 | b.append(self.values[j]) |
| 29 | j += 1 |
| 30 | |
| 31 | while i <= mid: |
| 32 | b.append(self.values[i]) |
| 33 | i += 1 |
| 34 | |
| 35 | while j <= high: |
| 36 | b.append(self.values[j]) |
| 37 | j += 1 |
| 38 | |
| 39 | for index, val in enumerate(b): |
| 40 | self.values[low + index] = val |