How to Merge two sorted arrays without using extra space?

To merge two sorted arrays without using extra space, please follow the below steps:

1. You can utilize the fact that both arrays are already sorted. 
2. You can perform an in-place merge by rearranging the elements in one of the arrays. 
3. Start from the last elements of both arrays and compare them.
4. Place the larger number at end of first array.
5. Decrease both the array index and move to the previous position.
6. Continue this process until all elements are processed.
7. if anything left in 2nd array then copy it at last of 1st array.

1

java
public class MergeSortedArrays {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1; // index of last element in nums1 
int j = n - 1; // index of last element in nums2

        int k = m + n - 1; // index of last position in merged array

        // Starting from the last elements of both arrays and comparing them 
while (i >= 0 && j >= 0) { 
if (nums1[i] >= nums2[j]) { 
 nums1[k] = nums1[i];
                i--;
 } else { 
 nums1[k] = nums2[j];
                j--; 
 } 
 k--; 
 } 
// If there are remaining elements in nums2, copy them to nums1

        while (j >= 0) {
nums1[k] = nums2[j];
            j--;
            k--; 
 } 
 } 
public static void main(String[] args) { 
int[] nums1 = {1, 3, 5, 0, 0, 0}; // sorted array with extra space for merging 
int[] nums2 = {2, 4, 6}; // sorted array 
int m = 3; // number of elements in nums1 
int n = 3; // number of elements in nums2 
 merge(nums1, m, nums2, n);

        // Print the merged array 
for (int num : nums1) { 
 System.out.print(num + " "); 
 }
 }
 }

The output of the given example would be: `1 2 3 4 5 6`, which represents the merged sorted array. 

Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo.

We could have use two way pointer approach if we would have only two values 0s and 1s but we have three 0s, 1s, and 2s, Now we can use the Dutch National Flag algorithm, also known as the 3-way partitioning algorithm. This algorithm separates the array into three sections: 0s, 1s, and 2s.

Here's an example implementation in Java:

java
public class Sort012 { 
public static void sortArray(int[] nums) {
int low = 0; 
int mid = 0;
int high = nums.length - 1; 
while (mid <= high) { 
if (nums[mid] == 0) { 
// Swap element at mid with element at low 
int temp = nums[low]; 
 nums[low] = nums[mid]; 
 nums[mid] = temp; 
 low++;
                mid++; 
 } else if (nums[mid] == 1) { 
// Move to the next element 
 mid++; 
 } else if (nums[mid] == 2) { 
// Swap element at mid with element at high 
int temp = nums[mid]; 
 nums[mid] = nums[high]; 
 nums[high] = temp; 
 high--; 
 }
 } 
 } 
public static void main(String[] args) { 
int[] nums = {2, 0, 1, 1, 0, 2, 1, 0}; 
System.out.println("Before sorting: " + Arrays.toString(nums));

        sortArray(nums); 
 System.out.println("After sorting: " + Arrays.toString(nums));
 } 
}

In this example, the array is {2, 0, 1, 1, 0, 2, 1, 0}. After sorting the array using the Dutch National Flag algorithm, the sorted array will be {0, 0, 0, 1, 1, 1, 2, 2}.

The algorithm maintains three pointers: low, mid, and high. The low pointer keeps track of the boundary of the section with 0s, the mid pointer scans the array, and the high pointer keeps track of the boundary of the section with 2s.

The algorithm traverses the array from left to right. If the element at the mid pointer is 0, it is swapped with the element at the low pointer, and both pointers are incremented. If the element at the mid pointer is 1, it is left in its place, and the mid pointer is incremented. If the element at the mid pointer is 2, it is swapped with the element at the high pointer, and the high pointer is decremented. This process continues until the mid pointer surpasses the high pointer, indicating that the array is sorted.