FilesExpand file tree

 master

/

Merge.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (48 loc) · 1.47 KB

 master

/

Merge.java

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (48 loc) · 1.47 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

public class Merge {

private static boolean less(Comparable a, Comparable b) {

return a.compareTo(b) < 0;

}

private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {

for (int k = low; k <= high; ++k) {

aux[k] = a[k];

}

int i = low;

int j = mid + 1;

for (int k = low; k <= high; k++) {

if (i > mid) {

a[k] = aux[j++];

} else if (j > high) {

a[k] = aux[i++];

} else if (less(a[j], a[i])) {

a[k] = aux[j++];

} else {

a[k] = aux[i++];

}

}

}

private static void sort(Comparable[] a, Comparable[] aux, int low, int high) {

if (low >= high) {

return;

}

int mid = low + (high - low) / 2;

sort(a, aux, low, mid);

sort(a, aux, mid + 1, high);

merge(a, aux, low, mid, high);

}

public static void sort(Comparable[] a) {

Comparable[] aux = new Comparable[a.length];

sort(a, aux, 0, a.length - 1);

}

public static void print(Object[] array) {

for (Object a: array) {

System.out.print(a + " ");

}

System.out.println("");

}

public static void main(String[] args) {

String[] array = {"Hope", "Eve", "Alice", "Charlie", "Tom", "Bob"};

Merge.print(array);

Merge.sort(array);

Merge.print(array);

}

}