Hey Ninjas! An essential subject for programming interviews is the Array. You'll discover that arrays are used in numerous problems, from complex to easy ones. Sorting is one of the crucial topics in data structure and algorithms. It is used to order the items specifically, and many other algorithms require sorting to function efficiently. There are many sorting algorithms like bubble sort, quick sort, and merge sort.

In this blog, we will discuss the creative sorting problem and the approach to solving the problem. Before diving into the solution, let’s discuss the problem statement briefly.

Problem Statement

Given an array consisting of integers. The main task is to find the largest sub-array in the given array, which is sorted. But, if the given array is not sorted, our task is to divide the array into halves (exactly from between) and check the corresponding two halves for sorting.

We aim to find the length of the largest sorted array possible from the given unsorted array with the condition mentioned.

Input

Total Number of elements in the array(N) = 8

Array = [1, 2, 9, 8, 4, 6, 8, 7]

Output

2

Explanation

Sorted subarrays possible when continuously dividing the arrays into halves are [1,2], and [4, 6]. Since the maximum size of sorted subarrays is 2, the answer to the input sample is 2.

Brute Force Approach

This is a straightforward and naive approach. It is possible to recursively divide an array and check whether each sub-array is sorted. If so, we give the length of the sub-array. If the parent subarray is sorted then the length of the current subarray is returned else the maximum value of each recursive function's left and right half subarrays is returned. Let’s take a look at the algorithm of the brute force approach.

Algorithm

Call the ‘max_sorted_subarray()’ function, which calculates the maximum sorted subarray by following the creative sort algorithm.

For the range [left, right] check if the subarray is sorted or not using the ‘is_sorted()’ function. If sorted, return the current size of the subarray. Else, call the ‘max_sorted_subarray()’ for the left half and right half.

Return the maximum of the answer of the left half and right half and display the result as the output.

Dry Run

The given array looks like this.

The first call is made to the whole array from index 0 to index 8, and it is checked whether the array is sorted or not.

As the current array is not sorted, the left and right halves are considered separately. The left half looks like this-

The second call is made to the subarray from index 0 to index 4 and is checked whether the array is sorted.

As the current array is not sorted the left and right halves are considered separately. The left half looks like this-

As the current subarray is sorted. Hence, 2 is returned from this recursive call which is the size of the current subarray.

The previous right half of the subarray is considered now, which looks like this.

As the current subarray is not sorted, the left and right halves are considered separately.

The left and right halves of this subarray contain a single element which is always sorted as the single element subarray is always sorted.

Similarly, like this, the recursive call occurs. Each time we get a subarray that is not sorted. The corresponding left, and right halves of the subarray are called and checked. Overall, after all, iterations, the answer for this array is 2.

#include <iostream>
#include <vector>
using namespace std;
/*
Function which checks if [left, right]
of array is sorted or not
*/
bool is_sorted(vector <int>& arr,int left, int right){
for(int i=left+1;i<right;i++){
// Current element less than previous element
if(arr[i] - arr[i-1] < 0){
return false;
}
}
return true;
}
// Function which returns maximum length of sorted subarray
int max_sorted_subarray(vector <int>& arr,int left,int right){
// When the array is sorted
if(is_sorted(arr,left,right)){
return (right-left);
}
int mid = (left + right) / 2;
// Evaluating maximum of the two halves subarrays
int lmax = max_sorted_subarray(arr,left,mid);
int rmax = max_sorted_subarray(arr,mid,right);
// Return the maximum of the two
return max(lmax,rmax);
}
int main() {
// Total number of elements in the array
int N = 8;
// Given elements of the array
vector <int> arr(N);
arr[0] = 1;
arr[1] = 2;
arr[2] = 9;
arr[3] = 8;
arr[4] = 4;
arr[5] = 6;
arr[6] = 8;
arr[7] = 7;
// Calling the function and displaying the output
cout<<max_sorted_subarray(arr,0,N);
}

Output

Implementation in Java

public class MyClass {
/*
Function which checks if [left, right]
of array is sorted or not
*/
static boolean is_sorted(int arr[],int left, int right){
for(int i=left+1;i<right;i++){
// Current element less than previous element
if(arr[i] - arr[i-1] < 0){
return false;
}
}
return true;
}
// Function which returns maximum length of sorted subarray
static int max_sorted_subarray(int arr[],int left,int right){
// When the array is sorted
if(is_sorted(arr,left,right)==true){
return (right-left);
}
int mid = (left + right) / 2;
// Evaluating maximum of the two halves subarrays
int lmax = max_sorted_subarray(arr,left,mid);
int rmax = max_sorted_subarray(arr,mid,right);
// Return the maximum of the two
return Math.max(lmax,rmax);
}
public static void main(String args[]) {
// Total number of elements in the array
int N = 8;
// Given elements of the array
int arr[] = new int [N];
arr[0] = 1;
arr[1] = 2;
arr[2] = 9;
arr[3] = 8;
arr[4] = 4;
arr[5] = 6;
arr[6] = 8;
arr[7] = 7;
// Calling the function and displaying the output
System.out.print(max_sorted_subarray(arr,0,N));
}
}

Output

Time Complexity

O(N^{2}) where ‘N’ is the total number of elements in the array

Explanation: In the worst case, on the last level there will be N recursive calls, and on the second level there will be N/2 recursive calls, and so on. The summation of N + N/2 + N/4 + .. up to infinite terms. The sum of these series is O(N). So, the recursive calls have a time complexity of O(N) and on each call, there will be an ‘is_sorted()’ function with a time complexity of O(N). Hence, the overall time complexity will be O(N^{2}).

Space Complexity

O(1)

Explanation: The auxiliary space complexity of the code is O(1) as there is no extra space used apart from the recursive calls, which are constant in space.

Efficient Approach

The problem is resolved using the merging technique of merge sort and recursion. Since an array of size one is already sorted, we may solve this issue by recursively splitting the current array in half and returning 1.

The function returns the length of the greatest sorted sub-array for each iteration. If the lengths of both sub-arrays are equal, we determine whether the left subarray's final element is smaller than the right subarray's opening element. We can observe that sub-arrays and the parent array are sorted under the above-mentioned circumstances. Thus, we give the length of the parent array.

If not, we compare the lengths from the two sub-arrays and return the longest possible length.

Algorithm

Call the ‘max_sorted_subarray()’ function, which calculates the maximum sorted subarray by following the creative sort algorithm.

If the left and the right difference is one, then return one as the array is of a single element.

Otherwise, store the answer for the left half in ‘lmax’ and the answer for the right half in ‘rmax’.

If the ‘lmax’ plus ‘rmax’ is equal to the size of the current subarray and arr[mid-1] is less than equal to arr[mid], then return the sum of ‘lmax’ and ‘rmax’.

Return the maximum of the ‘lmax’ and ‘rmax’.

Return the maximum answer of the left half and right half and display the result as the output.

Dry Run

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;
// Function which returns the maximum length of the sorted subarray
int max_sorted_subarray(vector <int>& arr,int left,int right){
// When the array length is 1
if(left == right - 1){
return 1;
}
// Evaluating the middle index
int mid = (left + right) / 2;
// Evaluating the maximum of the two halves subarrays
int lmax = max_sorted_subarray(arr,left,mid);
int rmax = max_sorted_subarray(arr,mid,right);
// Length of the current array
int len = right - left;
/*
Condition to check if the whole
array from left to right is sorted.
*/
if(lmax + rmax == len && arr[mid-1] <= arr[mid]){
return lmax + rmax;
}
// Return a maximum of the two
return max(lmax,rmax);
}
int main() {
// Total number of elements in the array
int N = 8;
// Given elements of the array
vector <int> arr(N);
arr[0] = 1;
arr[1] = 2;
arr[2] = 9;
arr[3] = 8;
arr[4] = 4;
arr[5] = 6;
arr[6] = 8;
arr[7] = 7;
// Calling the function and displaying the output
cout<<max_sorted_subarray(arr,0,N);
}

Output

Implementation in Java

public class MyClass {
// Function which returns the maximum length of the sorted subarray
static int max_sorted_subarray(int arr[],int left,int right){
// When the array length is 1
if(left == right - 1){
return 1;
}
// Evaluating the middle index
int mid = (left + right) / 2;
// Evaluating the maximum of the two halves subarrays
int lmax = max_sorted_subarray(arr,left,mid);
int rmax = max_sorted_subarray(arr,mid,right);
// Length of the current array
int len = right - left;
/*
Condition to check if the whole
array from left to right is sorted.
*/
if(lmax + rmax == len && arr[mid-1] <= arr[mid]){
return lmax + rmax;
}
// Return a maximum of the two
return Math.max(lmax,rmax);
}
public static void main(String args[]) {
// Total number of elements in the array
int N = 8;
// Given elements of the array
int arr[] = new int [N];
arr[0] = 1;
arr[1] = 2;
arr[2] = 9;
arr[3] = 8;
arr[4] = 4;
arr[5] = 6;
arr[6] = 8;
arr[7] = 7;
// Calling the function and displaying the output
System.out.print(max_sorted_subarray(arr,0,N));
}
}

Output

Time Complexity

O(N), where N is the total number of elements in the array

Explanation: In the worst case, on the last level there will be N recursive calls, on the second level there will be N/2 recursive calls, and so on. The summation of N + N/2 + N/4 + .. up to infinite terms. The sum of these series is O(N). So, the recursive calls have a time complexity of O(N).

Space Complexity

O(1)

Explanation: The auxiliary space complexity of the code is O(1) as there is no extra space used apart from the recursive calls which are constant in space.

Frequently Asked Questions

What is an Array?

An array is a data structure that sequentially stores an element of the same data type. In C/C++ or any other programming language, an array is a collection of similar data items. The data items are always stored in an array at contiguous memory locations.

Which is the fastest sorting technique?

Quicksort is considered the quickest sorting algorithm because its time complexity is O( N log N) in the best and almost average case scenarios, and in the worst case, it goes up to O (N ^ 2). Thus, it has the upper hand in most cases.

What is the best time complexity for solving the creative sorting problem?

The best time complexity for solving the creative sorting problem is O(N), where N is the total number of elements in the array.

What is the time complexity of mergesort?

The worst-case and average time complexity of mergesort is O(N*log(N)).

What is the underlying algorithm of the sort() function in C++?

The sort() function uses IntroSort. IntroSort is a hybrid sorting technique that uses Quicksort, Heapsort, and Insertion sort to minimize the running time.

Conclusion

Sorting algorithms are important as searching elements in a sorted array becomes easier than in an unsorted array. Overall, the time complexity of searching for an element is significantly reduced, which plays an essential role in programming. Some real-life applications of sorting algorithms are a contact list on your phone, a music playlist on your phone, and so on.

In this blog, we discussed the topic of the counting sort algorithm and the working of the algorithm. We also implemented the algorithm in two different languages C++ and Java. Sorting algorithms are also an essential topic in view of interview preparations and placement. It is, therefore, imperative to become an expert with sorting algorithms, understand what goes underneath the hood, and where you can apply your learnings.