Skip to content

Instantly share code, notes, and snippets.

@paullewallencom
Created July 26, 2018 17:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save paullewallencom/095fa79051dea092faa4402148fe0979 to your computer and use it in GitHub Desktop.
Save paullewallencom/095fa79051dea092faa4402148fe0979 to your computer and use it in GitHub Desktop.
Merge Sort
public class Merge
{
private Merge() { }
private static void merge( Comparable[] a, Comparable[] aux, int lo, int mid, int hi )
{
assert isSorted( a, lo, mid );
assert isSorted( a, mid + 1, hi );
for ( int k = lo; k <= hi; k++ )
{
aux[ k ] = a[ k ];
}
int i = lo, j = mid+1;
for ( int k = lo; k <= hi; k++ )
{
if ( i > mid ) a[ k ] = aux[ j++ ];
else if ( j > hi ) a[ k ] = aux[ i++ ];
else if ( less( aux[ j ], aux[ i ] ) ) a[ k ] = aux[ j++ ];
else a[ k ] = aux[ i++ ];
}
assert isSorted( a, lo, hi );
}
private static void sort( Comparable[] a, Comparable[] aux, int lo, int hi )
{
if ( hi <= lo ) return;
int mid = lo + ( hi - lo ) / 2;
sort( a, aux, lo, mid );
sort( a, aux, mid + 1, hi );
merge( a, aux, lo, mid, hi );
}
public static void sort( Comparable[] a )
{
Comparable[] aux = new Comparable[ a.length ];
sort( a, aux, 0, a.length - 1 );
assert isSorted( a );
}
private static boolean less( Comparable v, Comparable w )
{ return v.compareTo( w ) < 0; }
private static boolean isSorted( Comparable[] a )
{ return isSorted( a, 0, a.length - 1 ); }
private static boolean isSorted( Comparable[] a, int lo, int hi )
{
for ( int i = lo + 1; i <= hi; i++ )
if ( less( a[ i ], a[ i - 1 ] ) ) return false;
return true;
}
private static void merge( Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi )
{
for ( int k = lo; k <= hi; k++ )
{
aux[ k ] = index[ k ];
}
int i = lo, j = mid+1;
for ( int k = lo; k <= hi; k++ )
{
if ( i > mid ) index[ k ] = aux[ j++ ];
else if ( j > hi ) index[ k ] = aux[ i++ ];
else if ( less( a[ aux[ j ] ], a[ aux[ i ] ] ) ) index[ k ] = aux[ j++ ];
else index[ k ] = aux[ i++ ];
}
}
public static int[] indexSort( Comparable[] a )
{
int n = a.length;
int[] index = new int[ n ];
for ( int i = 0; i < n; i++ )
index[ i ] = i;
int[] aux = new int[ n ];
sort( a, index, aux, 0, n - 1 );
return index;
}
private static void sort( Comparable[] a, int[] index, int[] aux, int lo, int hi )
{
if ( hi <= lo ) return;
int mid = lo + ( hi - lo ) / 2;
sort( a, index, aux, lo, mid );
sort( a, index, aux, mid + 1, hi );
merge( a, index, aux, lo, mid, hi );
}
private static void show( Comparable[] a )
{
for ( int i = 0; i < a.length; i++ )
{
StdOut.println( a[ i ] );
}
}
public static void main( String[] args )
{
String[] a = StdIn.readAllStrings();
Merge.sort( a );
show( a );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment