fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Ideone
  7. {/* DESCRIPTION OF mergeThreeWay ALGORITHM
  8.      * 
  9.      * merges sorted subarrays A[start...firstThird], A[firstThird+1,secondThird], and A[secondThird+1,stop]
  10.      * 
  11.      * There are 3 possible cases when one merges :
  12.      *  1) all 3 sub-arrays have elements left
  13.      *  2) only 2 sub-arrays have elements left
  14.      *  3) only 1 sub-arrays have elements
  15.      *  
  16.      * What action to take?
  17.      *  For case 1) select the smallest element from the 3 sub-arrays and add it to the temporary array
  18.      *           2) select the smallest element from the 2 sub-arrays and add it to the temporary array
  19.      *           3) this sub-array is sorted - add all elements to the temporary array
  20.      * 
  21.      * Finally, copy the temporary array to the original array
  22.      * 
  23.      * The algorithm uses while loops to iterate trough the sub-arrays until one sub-array has no elements left (all of its elements have been copied to the temp array)
  24.      */
  25.     public static void mergeThreeWay(int A[], int start, int firstThird, int secondThird, int stop) {
  26.         int p1 = start;
  27.         int p2 = firstThird;
  28.         int p3 = secondThird;
  29.  
  30.         int tmp[] = new int[A.length];  // I need a temporary array of the same size as A because the sub-arrays keep their index, for example, a sub-array would look like this : [0, 0, 0, 0, 2, 9, 0, 0, 0, 0]  
  31.         int tmpIndex = start;
  32.  
  33.         // As long as tmpIndex as not reached the end of the array, execute the loop
  34.         while(tmpIndex <= stop) {
  35.  
  36.             // Get the smallest elements of the three sub-arrays
  37.             while (p1 < firstThird && p2 < secondThird && p3 <= stop) {
  38.                 if (A[p1] <= A[p2] && A[p1] <= A[p3]) {
  39.                     tmp[tmpIndex++] = A[p1++];
  40.                 }
  41.                 else if (A[p2] <= A[p1] && A[p2] <= A[p3]) {
  42.                     tmp[tmpIndex++] = A[p2++];
  43.                 }
  44.                 else if (A[p3] <= A[p1] && A[p3] <= A[p2]) {
  45.                     tmp[tmpIndex++] = A[p3++];
  46.                 } else {
  47.                     tmpIndex++;
  48.                 }
  49.             }
  50.  
  51.             // Get the smallest elements of the two remaining sub-arrays
  52.             while (p1 < firstThird && p2 < secondThird) {
  53.                 if (A[p1] <= A[p2]){
  54.                     tmp[tmpIndex++] = A[p1++];
  55.                 } else{
  56.                     tmp[tmpIndex++] = A[p2++];
  57.                 }
  58.             }
  59.  
  60.             while (p1 < firstThird && p3 < stop) {
  61.                 if (A[p1] <= A[p3]) {
  62.                     tmp[tmpIndex++] = A[p1++];
  63.                 } else {
  64.                     tmp[tmpIndex++] = A[p3++];
  65.                 }
  66.             }
  67.  
  68.             while (p2 < secondThird && p3 < stop) {
  69.                 if (A[2] <= A[p3]) {    
  70.                     tmp[tmpIndex++] = A[p2++];
  71.                 } else {
  72.                     tmp[tmpIndex++] = A[p3++];
  73.                 }
  74.             }
  75.  
  76.             // Complete with the remaining elements
  77.  
  78.             while (p1 < firstThird) tmp[tmpIndex++] = A[p1++];
  79.  
  80.             while (p2 < secondThird) tmp[tmpIndex++] = A[p2++];
  81.  
  82.             while (p3 <= stop) tmp[tmpIndex++] = A[p3++];
  83.  
  84.             tmpIndex++;
  85.         }
  86.  
  87.         System.out.println(Arrays.toString(tmp));
  88.         for(int k=start; k <= stop; k++) {
  89.             A[k] = tmp[k];
  90.         }
  91.     }
  92. 	public static void main (String[] args) throws java.lang.Exception
  93. 	{
  94. 		int myArray[] = {8,3,5,7,9,2,3,5,5,6};
  95. 		mergeThreeWay(myArray,0,1,5,9);
  96. 	}
  97. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[2, 3, 3, 5, 5, 5, 6, 7, 8, 9]
https://ideone.com/95AR6I
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!