Trusted answers to developer questions

Muhammad Saad Mehmoon

In this Answer, we'll go through merge sort (see the general implementation here) and modify it to sort elements only between two given indices.

Merge sort is an algorithm that uses a divide-and-conquer strategy to sort an array. This algorithm splits an array into two halves, sorts those halves, and then merges them back together.

To sort the array between two given indices, perform the following steps:

- The array is split at the starting and the ending index such that we get three arrays; the initial elements, the elements that need to be sorted, and the remaining elements.
- Merge sort is applied to the separated array.
- All three arrays are combined using concatenation.

Let's look at the code below:

def merge_sort(start, end, array): if len(array) <= 1: return array if start or end: return array[:start] + merge_sort(None, None, array[start:end+1]) + array[end+1:] mid = len(array)//2 first_half = merge_sort(None, None, array[:mid]) second_half = merge_sort(None, None, array[mid:]) i = 0 j = 0 new_array = [] while len(new_array) < len(first_half) + len(second_half): if i == len(first_half): new_array.extend(second_half[j:]) break if j == len(second_half): new_array.extend(first_half[i:]) break if first_half[i] < second_half[j]: new_array.append(first_half[i]) i += 1 else: new_array.append(second_half[j]) j += 1 return new_array start_point = 2 end_point = 6 array = [9, 1, 5, 3, 2, 10, 15, 4, 7] print(merge_sort(start_point, end_point, array))

Sorting an array between given indices using recursive merge sort

- Lines 3 and 4: We use the array splicing to split the array at the start and end points. Then, we apply the Merge sort, and different parts of the array are concatenated together and returned.
- Lines 7 to 9: We have a
`mid`

that stores the midpoint of the array, and then the array is divided into two parts which are stored in`first_half`

and`second_half`

, respectively. - Lines 14 to 27: We have a
`while`

loop that goes through the sorted halves in order and merges them.

Note:Lines 31 to 33 set a start index, an end index and the array to sort. You may change those values to see how the code behaves.

Merge sort has a time complexity of

RELATED TAGS

python

array

merge

CONTRIBUTOR

Muhammad Saad Mehmoon

RELATED COURSES

View all Courses

Keep Exploring

Related Courses