Theory: -
Sorting Half of an Array in Ascending and the Other Half in Descending Order
Problem Statement
Given an array of integers, the task is to sort the first half of the array in
ascending order and the second half in descending order.
Key Concepts
1. Array Splitting:
- The array is divided into two parts based on its midpoint.
- For an array of length ‘n’, the midpoint ‘mid’ is calculated as ‘(n + 1) / 2’.
This ensures that:
- If ‘n’ is even, the first half contains exactly ‘n/2’ elements.
- If ‘n’ is odd, the first half contains ‘(n + 1)/2’ elements (including the
middle element).
2. Sorting:
- First Half (Ascending Order): The elements from index ‘0’ to ‘mid – 1’ are
sorted in ascending order using a standard sorting algorithm (e.g.,
‘Arrays.sort’ in Java).
- Second Half (Descending Order):
- The elements from index ‘mid’ to ‘n – 1’ are first sorted in ascending
order.
- The sorted segment is then reversed to achieve descending order.
Reversing is done by swapping elements symmetrically around the center of
the segment.
3. Time Complexity:
- Sorting the first half: \(O(\frac{n}{2} \log \frac{n}{2})\).
- Sorting and reversing the second half: \(O(\frac{n}{2} \log \frac{n}{2} +
\frac{n}{2})\).
- Overall time complexity: \(O(n \log n)\), dominated by the sorting steps.
4. Space Complexity:
- The algorithm operates in-place, using only a constant amount of extra
space for swapping elements. Thus, the space complexity is \(O(1)\).
Algorithm Steps
1. Input: Read the array size and elements from the user.
2. Midpoint Calculation: Compute ‘mid = (n + 1) / 2’.
3. Sort First Half: Sort the subarray ‘arr[0..mid-1]’ in ascending order.
4. Sort and Reverse Second Half:
- Sort the subarray ‘arr[mid..n-1]’ in ascending order.
- Reverse the sorted subarray to get descending order.
5. Output: Print the modified array.
Example
Input Array: [5, 2, 4, 7, 9, 3, 1, 6, 8] (length n = 9)
- Midpoint: mid = (9 + 1) / 2 = 5
- First Half (Indices 0 to 4): [5, 2, 4, 7, 9] → Sorted to [2, 4, 5, 7, 9]
- Second Half (Indices 5 to 8): [3, 1, 6, 8] → Sorted to [1, 3, 6, 8] → Reversed
to [8, 6, 3, 1]
- Final Array: [2, 4, 5, 7, 9, 8, 6, 3, 1]
Applications :-
- This technique is useful in scenarios where data needs to be partially
ordered for efficient searching or visualization.
- It can be adapted for problems requiring hybrid sorting strategies, such as
organizing data with different priority orders.
Algorithm: -
BEGIN
PRINT “Enter the size of the array: ”
READ size
DECLARE array[size]
PRINT “Enter the elements of the array:”
FOR I = 0 TO size – 1
READ array[i]
END FOR
Mid = (size + 1) / 2
SORT array[0..mid-1] in ascending order
SORT array[mid..size-1] in ascending order
Start = mid
End = size – 1
WHILE start < end
SWAP array[start] and array[end]
Start = start + 1
End = end – 1
END WHILE
PRINT “Sorted array with first half in ascending and second half in
descending order:”
PRINT array
END
Code :-
import java.util.Arrays;
import java.util.Scanner;
class HalfSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int size = scanner.nextInt();
int[] array = new int[size];
System.out.println("Enter the elements of the array:");
for (int i = 0; i < size; i++) {
array[i] = scanner.nextInt();
sortHalf(array);
System.out.println("Sorted array with first half in ascending and second
half in descending order:");
System.out.println(Arrays.toString(array));
scanner.close();
public static void sortHalf(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
int n = arr.length;
int mid = (n + 1) / 2;
Arrays.sort(arr, 0, mid);
Arrays.sort(arr, mid, n);
int start = mid;
int end = n - 1;
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
Conclusion :-
By splitting the array into two halves and applying different sorting strategies
to each, we achieve a hybrid order that meets specific requirements
efficiently. The algorithm leverages standard sorting and reversing
operations, ensuring clarity and optimal performance.
