| |
Merge Sort -- O(n*logn) |
|
|
Subject: Merge Sort -- O(n*logn)
Author: Alex_Raj
In response to: Heap Sort -- O(n*logn)
Posted on: 12/27/2013 02:01:30 AM
/**
* Average case performance: O(nlogn)
* Best case performance: O(nlogn)
* Worst case performance: O(nlogn)
*/
public class MergeSort {
/**
* @param a Array of integers which are sorted when returns.
*/
public static void sort(int[] a){
int[] help = new int[a.length];
mergeSort(a, help, 0, a.length);
}
/**
* @param src Array of integers
* @param dest Helper array
* @param low Low index of array
* @param high High index of array
*/
private static void mergeSort(int[] src, int[] dest, int low, int high)
{
int len = high - low;
if(len==1){
dest[low] = src[low];
return;
}
int mid = (low+high)>>>1;
// split
mergeSort(src, dest, low, mid);
mergeSort(src, dest, mid, high);
// merge
int p1 = low;
int p2 = mid;
for(int k=low; k<high; k++){
if(p1<mid&&p2<high){
if(dest[p1]<=dest[p2]){ // '=' for stable
src[k] = dest[p1++];
}else{
src[k] = dest[p2++];
}
}else if(p1<mid){
src[k] = dest[p1++];
}else if(p2<high){
src[k] = dest[p2++];
}
}
// copy back to dest
for(int k=low; k<high; k++){
dest[k] = src[k];
}
}
}
>
> On 12/27/2013 02:00:13 AM Alex_Raj wrote:
/**
* Average case performance: O(nlogn)
* Best case performance: O(nlogn)
* Worst case performance: O(nlogn)
*/
public class HeapSort {
/**
* @param a Array of integers which are sorted when returns.
*/
public static void sort(int[] a){
/* Insertion onto heap */
for(int k=0; k<a.length; k++){
int n = k;
while(n>0){
int p = (n-1)/2; // parent
if(a[n]>a[p]){
swap(a, n, p);
n = p;
}else{
break;
}
}
}
/* Removal from heap */
for(int k=a.length-1; k>0; k--){
swap(a, 0, k);
maxHeap(a, k, 0);
}
}
/**
* @param a Array of integers
* @param size The heapsize
* @param p The starting point/parent to heapify
*/
private static void maxHeap(int[] a, int size, int p)
{
int left = 2*p + 1;
int right = left + 1;
// leaf node
if(left>=size)
return;
// node with only left child
if(right>=size){
if(a[left]>a[p]){
swap(a, left, p);
}
return;
}
// find the largest among node, left child and right child.
int largest = p;
if(a[left]>a[p])
largest = left;
if(a[right]>a[largest])
largest = right;
if(largest!=p){
swap(a, p, largest);
maxHeap(a, size, largest);
}
}
private static void swap(int[] a, int j, int k) {
int temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}
References:
|
|
|
|
