Trusted answers to developer questions
How to sort an array between two indices using merge sort
Muhammad Saad MehmoonOverview
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
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.
Steps
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.
1 of 18
Code example
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
Code explanation
- 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
midthat stores the midpoint of the array, and then the array is divided into two parts which are stored infirst_halfandsecond_half, respectively. - Lines 14 to 27: We have a
whileloop 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.
Time complexity
Merge sort has a time complexity of
RELATED TAGS
python
array
merge
CONTRIBUTOR
Muhammad Saad MehmoonRELATED COURSES
View all Courses
Keep Exploring
Related Courses
