Posts Merge Sort
Post
Cancel

Merge Sort

Problem Description

Implement Merge Sort.

Solution

We will make use of a problem we solved earlier: Sort a sub-array given s,m,e. If we carefully think about any given array, we can divide it into two parts -> Sort them separately -> Then merge both sorted array. For the first half of the array, we can again sort it in the same way. And keep doing it recursively until we have just a single element (which is going to be our base case). Since we have a merge function which takes s, m and e we can use this to merge two sorted array. The important part of the merge function is our assumption. The assumption we take for this recursive function is: Given A[], sort it from start(s) to end(e)

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
53
54
55
56
57
58
59
60
61
62
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};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void mergeSort(int[] arr, int s, int e){

        if(s==e) return;
        int m = (s+e)/2;
        mergeSort(arr, s, m);
        mergeSort(arr, m+1, e);
        merge(arr, s, m, e);

    }

    //Given an array and index s, m and e, Sort the sub-array from s to e. Consider [s,m] and [m+1,e] is already sorted
    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.