• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 18th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Static  int[] mergeSort(int[] lst) {
2.     int n = lst.length;
3.     int[] left;
4.     int[] right;
5.
6.     // create space for left and right subarrays
7.     if (n % 2 == 0) {
8.         left = new int[n/2];
9.         right = new int[n/2];
10.     }
11.     else {
12.         left = new int[n/2];
13.         right = new int[n/2+1];
14.     }
15.
16.     // fill up left and right subarrays
17.     for (int i = 0; i < n; i++) {
18.         if (i < n/2) {
19.             left[i] = lst[i];
20.         }
21.         else {
22.             right[i-n/2] = lst[i];
23.         }
24.     }
25.
26.     // recursively split and merge
27.     left = mergeSort(left);
28.     right = mergeSort(right);
29.
30.     // merge
31.     return merge(left, right);
32. }
33. // the function for merging two sorted arrays
34. static int[] merge(int[] left, int[] right) {
35.     // create space for the merged array
36.     int[] result = new int[left.length+right.length];
37.
38.     // running indices
39.     int i = 0;
40.     int j = 0;
41.     int index = 0;
42.
43.     // add until one subarray is deplete
44.     while (i < left.length && j < right.length) {
45.         if (left[i] < right[j]) {
46.             result[index++] = left[i++];
47.         {
48.         else {
49.             result[index++] = right[j++];
50.         }
51.     }
52.
53.     // add every leftover elelment from the subarray
54.     while (i < left.length) {
55.         result[index++] = left[i++];
56.     }
57.
58.     // only one of these two while loops will be executed
59.     while (j < right.length) {
60.         result[index++] = right[j++];
61.     }
62.
63.     return result;
64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top