Problem Description
Give an array of N elements and three indices s, m and e in which [s,m] sub-array is sorted and [m+1,e] is also sorted. You need to sort the complete sub-array from [s,e].
Solution
We can consider the two sub-arrays [s,m] and [m+1,e] as two different arrays which are sorted and then use a two pointer approach to join them. We can use a temporary array of size (e-s+1) which will have the elements from s to e in a sorted way. Finally, simply replace the elements in this temporary array to the original array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package com.gauk;
import java.util.Arrays;
public class Sorting {
public static void main(String[] args) {
int[] arr = new int[]{4,8,-1,2,6,3,4,7,13,0};
merge(arr, 2, 4, 7);
System.out.println(Arrays.toString(arr));
}
public static void merge(int[] arr, int s, int m, int e){
int[] temp = new int[e-s+1];
int i=s;
int j=m+1;
int idx=0;
while(i<=m && j<=e){
if(arr[i] < arr[j]){
temp[idx] = arr[i];
i++;
}else{
temp[idx] = arr[j];
j++;
}
idx++;
}
for(int x=i; x<=m; x++){
temp[idx] = arr[x];
idx++;
}
for(int x=j; x<=e; x++){
temp[idx] = arr[x];
idx++;
}
for(int w=s; w<=e; w++){
arr[w] = temp[w-s];
}
}
}