FilesExpand file tree

 master

/

MergeSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

110 lines (93 loc) · 2.56 KB

 master

/

MergeSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

110 lines (93 loc) · 2.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

/*

1.Divide the array until each single element is found.

2.Merge all the single element based on their size

*/

package merge.sort;

/* Java program for Merge Sort */

class MergeSort

{

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

// Find sizes of two subarrays to be merged

int n1 = m - l + 1;

int n2 = r - m;

/* Create temp arrays */

int L[] = new int [n1];

int R[] = new int [n2];

/*Copy data to temp arrays*/

for (int i=0; i<n1; ++i)

L[i] = arr[l + i];

for (int j=0; j<n2; ++j)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays */

// Initial indexes of first and second subarrays

int i = 0, j = 0;

// Initial index of merged subarry array

int k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy remaining elements of L[] if any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy remaining elements of R[] if any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

// Main function that sorts arr[l..r] using

// merge()

void sort(int arr[], int l, int r)

{

if (l < r)

{

// Find the middle point

int m = (l+r)/2;

// Sort first and second halves

sort(arr, l, m);

sort(arr , m+1, r);

// Merge the sorted halves

merge(arr, l, m, r);

}

}

/* A utility function to print array of size n */

static void printArray(int arr[])

{

int n = arr.length;

for (int i=0; i<n; ++i)

System.out.print(arr[i] + " ");

System.out.println();

}

// Driver method

public static void main(String args[])

{

int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("Given Array");

printArray(arr);

MergeSort ob = new MergeSort();

ob.sort(arr, 0, arr.length-1);

System.out.println("\nSorted array");

printArray(arr);

}

}