Sort an Array

LeetCode Q 912 - Sort an Array

Given an array of integers nums, sort the array in ascending order.

Example 1:
Input: [5,2,3,1] ; Output: [1,2,3,5]

Example 2:
Input: [5,1,1,2,0,0] ; Output: [0,0,1,1,2,5]

Note:

• 1 <= A.length <= 10000
• -50000 <= A[i] <= 50000

Solution

Solution 1 : Counting sort

Code:

public int[] sortArray(int[] nums) {
	
	int[] count = new int[100001];

	for (int num: nums) 
		count[num + 50000]++;

	int res = new int[nums.length];
	int index = 0;

	for (int i = 0; i < 100001; i++) {
		while (count[i]-- != 0) 
			res[index++] = i - 50000;
	}

	return res;
}

Solution 2 : MergeSort

Code:

public int[] sortArray(int[] nums) {
	return mergeSort(nums, 0, nums.length - 1);
}

private int[] mergeSort(int[] nums, int left, int right) {
	if (left > right) return null;
	if (left == right) return new int[]{nums[left]};
	
	int mid = left + (right - left) / 2;
	
	int[] leftArray = mergeSort(nums, left, mid);
	int[] rightArray = mergeSort(nums, mid + 1, right);
	
	return merge(leftArray, rightArray);
}

private int[] merge(int[] left, int[] right) {
	
	int[] res = new int[left.length + right.length];
	int i = 0, j = 0, idx = 0;
	
	while (i < left.length || j < right.length) {
		int num1 = i == left.length ? 50001 : left[i];
		int num2 = j == right.length ? 50001 : right[j];
		
		if (num1 < num2) {
			res[idx++] = num1; i++;
		} else {
			res[idx++] = num2; j++;
		}
	}
	
	return res;
}

Solution 3 : QuickSort

Code:

public int[] sortArray(int[] nums) {
	quickSort(nums, 0, nums.length - 1);
	return nums;
}

private void quickSort(int[] nums, int left, int right) {
	
	if (left >= right) return;

	int p = partition(nums, left, right);

	quickSort(nums, left, p - 1);
	quickSort(nums, p + 1, right);
}

private int partition(int[] nums, int left, int right ) {
	
	int pivot = nums[left];
	
	while (left < right) {
	
		while (left < right && nums[right] >= pivot)
			right--;
	
		nums[left] = nums[right];

		while (left < right && nums[left] <= pivot)
			left++;
	
		nums[right] = nums[left];
	}

	nums[left] = pivot;

	return left;
}