deyanmalinov

Merge Sort

Jul 22nd, 2021
972
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.company;
  2.  
  3. public class Main {
  4.     public static void main(String[] args){
  5.         int[] nums = new int[]{5,6,2,8,1,9,3,4};
  6.         Sort(nums, 0, nums.length - 1);
  7.         Print(nums);
  8.  
  9.     }
  10.  
  11.     private static void Sort(int[] nums, int startInd, int endInd) {
  12.         //Arrays.sort(nums);
  13.         if (startInd >= endInd){
  14.             return;
  15.         }
  16.             int midInd = (startInd + endInd) / 2;
  17.  
  18.             Sort(nums, startInd, midInd);
  19.  
  20.             Sort(nums, midInd + 1, endInd);
  21.  
  22.             Merge(nums, startInd, midInd, endInd);
  23.     }
  24.  
  25.     private static void Merge(int[] nums, int startInd, int midInd, int endInd) {
  26.         if (midInd < 0 || midInd + 1 >= nums.length || nums[midInd] <= nums[midInd + 1]) {
  27.             return;
  28.         }
  29.         int[] tempNums = new int[nums.length];
  30.  
  31.         for (int i = startInd; i <= endInd; i++) {
  32.             tempNums[i] = nums[i];
  33.         }
  34.         int leftInd = startInd;
  35.         int rightInd = midInd+1;
  36.  
  37.         for (int i = startInd; i <= endInd; i++) {
  38.             if (leftInd > midInd) {
  39.                 nums[i] = tempNums[rightInd++];
  40.             } else if (rightInd > endInd) {
  41.                 nums[i] = tempNums[leftInd++];
  42.             } else if (tempNums[leftInd] <= tempNums[rightInd]) {
  43.                 nums[i] = tempNums[leftInd++];
  44.             } else {
  45.                 nums[i] = tempNums[rightInd++];
  46.             }
  47.         }
  48.     }
  49.     private static void Print(int[] nums){
  50.         for (int num : nums) {
  51.             System.out.print(num+" ");
  52.         }
  53.     }
  54. }
RAW Paste Data