Description
Given an integer array, sort it in ascending order in place. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.
Example
Example1:
Input: [3, 2, 1, 4, 5],
Output: [1, 2, 3, 4, 5].
Example2:
Input: [2, 3, 1],
Output: [1, 2, 3].
Solution1 - Merge Sort
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
if (A == null || A.length == 0)
return;
int[] newArray = new int[A.length];
sort(A, 0, A.length - 1, newArray);
}
private void sort(int[] A, int start, int end, int[] newArray) {
if (end <= start)
return;
int mid = start + (end - start) / 2;
sort(A, start, mid, newArray);
sort(A, mid + 1, end, newArray);
merge(A, newArray, start, end);
}
private void merge(int[] A, int[] newArray, int start, int end) {
int leftStart = start;
int mid = start + (end - start) / 2;
int rightStart = mid + 1;
int index = start;
while (leftStart <= mid && rightStart <= end) {
if (A[leftStart] < A[rightStart]) {
newArray[index] = A[leftStart];
leftStart++;
} else {
newArray[index] = A[rightStart];
rightStart++;
}
index++;
}
while (leftStart <= mid) {
newArray[index] = A[leftStart];
leftStart++;
index++;
}
while (rightStart <= end) {
newArray[index] = A[rightStart];
rightStart++;
index++;
}
// copy the sorted part back to the original array
for (int i = start; i <= end; i++) {
A[i] = newArray[i];
}
}
}
Solution2 - Quick Sort
public void sortIntegers2(int[] A) {
quicksort(A,0,A.length-1);
}
private void quicksort(int[] A, int start, int end){
if (start>=end)
return;
int pivot = A[(start+end)/2];
int left = start;
int right = end;
while(left<=right){
while(left<=right && A[left] < pivot)
left++;
while(left<=right && A[right] > pivot)
right++;
if (left<=right) {
int tmp = A[left];
A[left] = A[right];
A[right] = tmp;
left++;
right--;
}
}
quicksort(A ,start,right);
quicksort(A,left,end);
}