Sort an Array

Updated on 08 July, 2025
Sort an Array header image

Problem Statement

The task requires sorting an integer array nums in an ascending order without utilizing any built-in sorting functions. The solution must adhere to an O(nlog(n)) time complexity, aiming for optimal efficiency, and it should use the least amount of space possible. This problem tests one's understanding of sorting algorithms that can achieve this complexity and efficiency in space usage without relying on predefined functions.

Examples

Example 1

Input:

nums = [5,2,3,1]

Output:

[1,2,3,5]

Explanation:

After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2

Input:

nums = [5,1,1,2,0,0]

Output:

[0,0,1,1,2,5]

Explanation:

Note that the values of nums are not necessairly unique.

Constraints

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Approach and Intuition

To approach the problem of sorting an array without built-in functions, and to achieve an O(nlog(n)) time complexity, we can consider efficient sorting algorithms like Merge Sort or Quick Sort. These algorithms are well-suited for this scenario:

  1. Merge Sort:

    • Divide and Conquer Approach: Split the array into halves recursively until each sub-array contains a single element.
    • Merge Step: Recursively combine the sub-arrays back together by comparing their elements and assembling them in sorted order.
    • This method not only adheres to the required time complexity but is also stable and works well with linked lists.
    • However, Merge Sort typically uses extra space proportional to the size of the input array.
  2. Quick Sort:

    • Pivot Selection: Choose a pivot element from the array (various strategies can optimize pivot selection).
    • Partitioning: Reorganize the array so that elements less than the pivot come before it and elements greater come after it.
    • Recursive Sorting: Apply the same logic recursively to the partitions generated by the pivot.
    • Quick Sort reduces the extra space requirement as it can be implemented in-place. Nevertheless, its worst-case performance, although rare, is O(n^2), which can be avoided with good pivot selections such as choosing a median.

By avoiding built-in functions and directly implementing these algorithms, we gain a deeper understanding of their mechanics and avoid any hidden complexities that built-in implementations might entail. As per the constraints and needs of the problem, you might lean towards Merge Sort for stable sorting at the cost of space, or Quick Sort for an in-place solution with careful pivot selection to avoid degraded performances.

Solutions

  • C++
cpp
class Solution {
    // Sorting number based on digit utilzing bucket method
    void distributeToBuckets(vector<int>& numbers, int divisor) {
        vector<vector<int>> buckets(10);
        for (int& num : numbers) {
            int digit = (abs(num) / divisor) % 10;
            buckets[digit].push_back(num);
        }
    
        // Combine buckets back into original vector.
        int position = 0;
        for (auto &bucket : buckets) {
            for (int& num : bucket) {
                numbers[position++] = num;
            }
        }
    }
        
    // Organized sorting of integers.
    void performRadixSort(vector<int>& numbers) {
        int maximumVal = numbers[0];
        for (int i = 1; i < numbers.size(); i++) {
            if (abs(numbers[i]) > maximumVal) {
                maximumVal = abs(numbers[i]);
            }
        }
    
        int totalDigits = 0;
        while (maximumVal != 0) {
            totalDigits++;
            maximumVal /= 10;
        }
    
        // Conducting sorting per digit significancy.
        int base = 1;
        for (int currentDigit = 0; currentDigit < totalDigits; currentDigit++) {
            distributeToBuckets(numbers, base);
            base *= 10;
        }
    
        // Handle negative values correctly
        vector<int> negatives, nonNegatives;
        for (int num : numbers) {
            if (num < 0) {
                negatives.push_back(num);
            } else {
                nonNegatives.push_back(num);
            }
        }
        reverse(negatives.begin(), negatives.end());
    
        // Combine sorted parts.
        copy(negatives.begin(), negatives.end(), numbers.begin());
        copy(nonNegatives.begin(), nonNegatives.end(), numbers.begin() + negatives.size());
    }
    
public:
    vector<int> sortArray(vector<int>& nums) {
        performRadixSort(nums);
        return nums;
    }
};

Implement the array sorting functionality in C++ using radix sort, which is effective for sorting integers based on their digits. Follow these steps to understand the implemented solution:

  1. Define a helper function distributeToBuckets to distribute elements into buckets based on the current significant digit. The result is a set of buckets where each bucket contains numbers having the same digit at the current digit position.
  2. Reassemble numbers from buckets to the original array post-distribution to set the stage for the next significant digit sorting.
  3. Implement performRadixSort to manage the radix sorting process, which includes determining the maximum number of digits in the largest absolute number in the array.
  4. Execute the sorting logic digit by digit starting from the least significant digit to the most significant digit.
  5. Address negative numbers by separating them and reversing their order post all digit-based sorting to ensure they are sorted correctly.
  6. Merge the sorted negative and non-negative numbers back into the original array to produce the final sorted order.
  7. The sortArray public method initiates the sorting process by calling performRadixSort and returns the sorted array.

This approach effectively handles both positive and negative integers, adjusting for each digit's significance iteratively and ensures all numbers are returned in a non-decreasing order.

  • Java
java
class Solution {
    // Sort digits using bucket method.
    private void digitSort(int[] data, int exp) {
        ArrayList<List<Integer>> bucketList = new ArrayList<>(10);
        for (int i = 0; i < 10; ++i) {
            bucketList.add(i, new ArrayList<Integer>());
        }
            
        // Distribute elements to buckets based on current significant place digit.
        for (int num : data) {
            int digit = Math.abs(num) / exp % 10;
            bucketList.get(digit).add(num);
        }
    
        // Reassemble sorted elements back into the array.
        int pos = 0;
        for (List<Integer> bucket : bucketList) {
            for (int num : bucket) {
                data[pos++] = num;
            }
        }
    }
        
    // Implementation of radix sorting.
    private void sortUsingRadix(int[] data) {
        int largestNum = data[0];
        for (int num : data) {
            largestNum = Math.max(largestNum, Math.abs(num));
        }
    
        // Determine number of passes needed.
        int place = 1;
        while (largestNum > 0) {
            digitSort(data, place);
            place *= 10;
            largestNum /= 10;
        }
    
        // Segregation of negative and positive numbers.
        ArrayList<Integer> negativeNums = new ArrayList<>();
        ArrayList<Integer> positiveNums = new ArrayList<>();
        for (int num : data) {
            if (num < 0) negativeNums.add(num);
            else positiveNums.add(num);
        }
    
        Collections.reverse(negativeNums);  // Put negatives in descending order.
    
        // Update array with sorted numbers.
        int idx = 0;
        for (int num : negativeNums) {
            data[idx++] = num;
        }
        for (int num : positiveNums) {
            data[idx++] = num;
        }
    }
    
    public int[] sortArray(int[] elements) {
        sortUsingRadix(elements);
        return elements;
    }
}

The Java program provided outlines an implementation of the Radix Sort algorithm, specifically customized to handle negative numbers through a secondary process that segregates and orders them correctly. Below is a breakdown of how the Radix Sort system operates within this solution:

  • Instantiate a digit-sorting method termed 'digitSort' for arranging numbers in a given array based on their significant figures. Within this method:

    • Set up ten "buckets" to sort each number in the array based on the digit of current interest.
    • Populate each bucket with numbers categorized by the relevant digit - this is computed using mod and division operations.
    • Compile the array back by concatenating numbers retrieved sequentially from these buckets.
  • Develop the main sorting framework using a method named 'sortUsingRadix' where:

    • Determine the highest absolute value in the array to ascertain the number of digits and, consequently, the number of required sorting iterations.
    • Utilize 'digitSort' in each iteration to sort numbers based on the current significant digit.
    • Separate the sorted numbers into negative and positive groups.
    • Reverse the sorted negative numbers, ensuring they are placed in descending order to maintain sort consistency when joined with the ascending sorted positives.
    • Finally, merge these categorized numbers back into the original array in the correct order.
  • The top-level function 'sortArray' serves as a bridge, invoking the radix sorting method and returning the sorted array. This comprehensive setup ensures accurate sorting, keeping computational efficiency in check by leveraging the digit-based decomposition strategy of Radix Sort, further tailored to accommodate negative integers gracefully.

  • JavaScript
js
var sortedArray = function(array) {
    // Function to perform counting sort based on specific digit position.
    let countingSort = digitPlace => {
        let digitMap = {};
        // Mapping numbers based on their respective digit at place 'digitPlace'.
        array.forEach(element => {
            let digit = Math.floor(Math.abs(element) / digitPlace) % 10;
                
            if (!digitMap[digit]) {
                digitMap[digit] = [];
            }
            digitMap[digit].push(element);
        });
    
        // Re-create sorted 'array' using digitMap.
        let idx = 0;
        for (let i = 0; i < 10; ++i) {
            if (digitMap[i]) {
                digitMap[i].forEach(number => {
                    array[idx++] = number;
                });
            }
        }
    };
        
    // Function to perform radix sort.
    let radixSort = () => {
        // Determining the maximum number to figure out the number of digit places.
        let maxNumber = Math.max(...array.map(Math.abs));
        let digitCounts = 0;
        while (maxNumber > 0) {
            digitCounts++;
            maxNumber = Math.floor(maxNumber / 10);
        }
    
        // Sorting based on each digit place.
        let placeValue = 1;
        for (let i = 0; i < digitCounts; ++i) {
            countingSort(placeValue);
            placeValue *= 10;
        }
    
        // Separating negative and positive numbers.
        let negativePart = [];
        let positivePart = [];
        array.forEach(value => {
            if (value < 0) negativePart.push(value);
            else positivePart.push(value);
        });
        negativePart.reverse();
    
        // Combining the sorted parts.
        array = [...negativePart, ...positivePart];
    };
        
    // Call radix sort on the entire array.
    radixSort();
    return array;
};

The JavaScript solution provided implements a sorting algorithm for an array using the Radix Sort technique. This technique efficiently handles sorting by digit places, making it well-suited for handling large numbers. Below is how the solution accomplishes this:

  1. Define a helper function named countingSort, which sorts elements of the array based on the digits at a specific place value (digitPlace). The function constructs a map (digitMap) to collect elements by the digits they have at the current place value, effectively grouping them. This map is then used to reconstruct the original array in a sorted order concerning the current digit.

  2. Define another function named radixSort that handles the calculation of the maximum number of digits in any element in the array (maxNumber). It then iterates over these digits from the least significant to the most significant. For each digit place value, it calls countingSort to sort the array elements according to the current digit.

  3. Additionally, the radixSort function separates negative and positive numbers after all digit place-based sorting is done. This separation is necessary because radix sort typically only deals with non-negative numbers. Here, negative numbers are temporarily stored, sorted separately, and then reintegrated with positives, ensuring that the overall array order reflects the correct numerical values.

  4. Finally, the sorted array combines the reversed negative numbers followed by positive numbers, ensuring that negative values maintain their order but appear before positive values in the result.

  5. The main function sortedArray orchestrates the sort by calling radixSort and returning the sorted array.

This sorting routine is efficient for large datasets with large numbers as it focuses on digit-by-digit comparison, alleviating the drawbacks of comparison-based sorting methods. It optimizes performance by handling numbers sequentially based on their digit significance and properly segregating negative and positive values, ensuring stability and accuracy in the sorted results.

  • Python
python
class Solution:
    # Sorts integers using radix sort technique
    def sort_integers(self, integers: List[int]) -> List[int]:
        # Determine the largest number to define number of digit passes
        max_num = integers[0]
        for number in integers:
            max_num = max(abs(number), max_num)
    
        digit_count = 0
        while max_num > 0:
            digit_count += 1
            max_num //= 10
    
        radix = 1
            
        # Sort numbers with respect to each digit using bucket sort
        def sort_by_digit():
            digit_buckets = [[] for _ in range(10)]
            # Place each number in the appropriate bucket based on current digit
            for number in integers:
                place = abs(number) // radix
                bucket_index = int(place % 10)
                digit_buckets[bucket_index].append(number)
    
            # Flatten the bucket content back into the original array
            idx = 0
            for bucket in range(10):
                for number in digit_buckets[bucket]:
                    integers[idx] = number
                    idx += 1
    
        # Loop through digits from least to most significant
        for _ in range(digit_count):
            sort_by_digit()
            radix *= 10
    
        # Separate and sort negative numbers
        positives = [num for num in integers if num >= 0]
        negatives = [num for num in integers if num < 0]
        negatives.reverse()
    
        # Combine negatives in reverse with positives
        return negatives + positives
                
    def sortArray(self, integers: List[int]) -> List[int]:  
        return self.sort_integers(integers)

Sort an Array in Python using the Radix Sort technique provided in the given Python class Solution. This implementation of sorting provides a systematic handling of integers, especially optimizing the Radix Sort process. Follow these insights to understand how the code functions:

  • Initialize the sorting process by calculating the maximum absolute number from the list to determine the necessary number of digit passes for sorting.
  • Utilize a nested function sort_by_digit to perform radix sort for each digit position using a bucket sort approach. Numbers are placed in buckets based on the current significant digit, progressively adjusting the radix multiplier.
  • After sorting all digits from least significant to the most significant, negative numbers are separated, reversed, and then combined with the non-negative numbers to maintain their correct order when the sorted array is reconstructed.

This sorting implementation effectively manages both positive and negative integers by ensuring that the sorting maintains stability, a crucial factor for bucket and radix sorts. The final sorted array merges negatives (in reverse order) and positives, ensuring that all integers are in their correct positions according to their values.

Comments

No comments yet.