Related Tags

python
array
merge

# How to sort an array between two indices using merge sort

### Overview

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:

1. 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.
2. Merge sort is applied to the separated array.
3. 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 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.

#### Time complexity

Merge sort has a time complexity of $\mathcal{O}(nlogn).$ It is because the merging process takes $\mathcal{O}(n)$ and the list is split in half at every step, which takes $\mathcal{O}(logn)$.

RELATED TAGS

python
array
merge

CONTRIBUTOR