×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Java
Posted by: Shamir Yona
Added: Jun 18, 2016 12:28 PM
Views: 13
Tags: sort java merge
An implementation of optimal space saving Merge Sort.
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package moreTests;
  7.  
  8. import java.util.Arrays;
  9.  
  10. /**
  11.  *
  12.  * @author shayzukerman
  13.  */
  14. public class MergeSort
  15. {
  16.     int[] inpArr;
  17.     int N; // Size of the input array
  18.    
  19.     int[] tmpArr; //Helper array
  20.  
  21.     public MergeSort(int[] inpArr)
  22.     {
  23.         this.inpArr = inpArr;
  24.         N = inpArr.length;
  25.         tmpArr = new int[N];
  26.     }
  27.    
  28.    
  29.     public void mergeSort()
  30.     {
  31.         mergeSort_aux(0, N - 1, 0);
  32.     }
  33.    
  34.     private void mergeSort_aux(int min, int max, int dbg_level)
  35.     {
  36.         printRange(min, max, String.format("start - level: %d ", dbg_level));
  37.         if (min >= max)
  38.             return;
  39.         int mid = min + (max - min) / 2;
  40.         mergeSort_aux(min, mid, dbg_level + 1);
  41.         mergeSort_aux(mid + 1, max, dbg_level + 1);
  42.         sortParts(min, mid, max);
  43.     }
  44.    
  45.     private void sortParts(int min, int mid, int max)
  46.     {
  47.         int i = min;
  48.         int j = mid + 1;
  49.         int k = 0;
  50.        
  51.     //    System.out.println("mid: " + mid);
  52.     //    printRange(min, max, "In sortParts - start");
  53.         Arrays.fill(tmpArr, 0);
  54.        
  55.         while (i <= mid && j <= max)
  56.         {
  57.             if (inpArr[i] < inpArr[j])
  58.             {
  59.                 tmpArr[k++] = inpArr[i];
  60.                 i++;
  61.             }
  62.             else
  63.             {
  64.                 tmpArr[k++] = inpArr[j];
  65.                 j++;
  66.             }
  67.         }
  68.         while (i <= mid)
  69.             tmpArr[k++] = inpArr[i++];
  70.  
  71.         while (j <= max)
  72.             tmpArr[k++] = inpArr[j++];
  73.            
  74.         System.arraycopy(tmpArr, 0, inpArr, min, max - min + 1);
  75.   //      printRange(min, max, "In sortParts - end");
  76.        
  77.     }
  78.    
  79.     private void printRange(int min, int max, String msg)
  80.     {
  81.         System.out.format("%s - min: %d max: %d - [", msg, min, max);
  82.         while (min <= max)
  83.         {
  84.             System.out.format("%d%s", inpArr[min], ((min < max) ? ", " : ""));
  85.             min++;
  86.         }
  87.         System.out.println("]");
  88.     }
  89.    
  90.    
  91.     public static void main(String[] args)
  92.     {
  93.         int[] inpArr = {8, 294, 20, 2,96, 1,6,3,9,4,1000, 5,10, 123};
  94.         MergeSort ms = new MergeSort(inpArr);
  95.         ms.mergeSort();
  96.         ms.printRange(0, inpArr.length - 1, "After sort");
  97.     }
  98.  
  99.  
  100. }
  101.