Posts Sort Sub-Array in Array Given s,m,e
Post
Cancel

Sort Sub-Array in Array Given s,m,e

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];
        }

    }

}
This post is licensed under CC BY 4.0 by the author.