Skip to content

Instantly share code, notes, and snippets.

@rishi93
Last active November 10, 2015 06:46
Show Gist options
  • Save rishi93/c690813571c2f7feff61 to your computer and use it in GitHub Desktop.
Save rishi93/c690813571c2f7feff61 to your computer and use it in GitHub Desktop.
Merge Sort in Java
import java.io.*;
class Ideone
{
static int[] slice(int[] arr, int start, int end)
{
int[] result = new int[end-start];
for(int i = 0; i < result.length; i ++)
{
result[i] = arr[start+i];
}
return result;
}
static void printArray(int[] arr)
{
for(int i = 0;i < arr.length; i++)
{
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
}
static int[] mergesort(int[] arr)
{
if(arr.length <= 1)
{
return arr;
}
int mid = arr.length / 2;
int[] left = slice(arr,0,mid);
int[] right = slice(arr,mid,arr.length);
left = mergesort(left);
right = mergesort(right);
return merge(left,right);
}
static int[] merge(int[] left, int[] right)
{
int[] result = new int[left.length + right.length];
int result_index = 0;
int left_index = 0,right_index = 0;
while(left_index < left.length && right_index < right.length)
{
if(left[left_index] < right[right_index])
{
result[result_index] = left[left_index];
result_index += 1;
left_index += 1;
}
else
{
result[result_index] = right[right_index];
result_index += 1;
right_index += 1;
}
}
while(left_index < left.length)
{
result[result_index] = left[left_index];
result_index += 1;
left_index += 1;
}
while(right_index < right.length)
{
result[result_index] = right[right_index];
result_index += 1;
right_index += 1;
}
return result;
}
public static void main (String[] args)
{
int[] arr = {6,5,1,3,2,4};
printArray(mergesort(arr));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment