We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort an Array

Number: 948

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Meta, Bloomberg, Yahoo, Adobe, Apple, Uber

Problem Description

Given an array of integers, the goal is to sort the array in ascending order without using any built-in sort functions. The solution must run in O(nlog(n)) time and use as little extra space as possible.

Key Insights

  • Must not use built-in functions.
  • Achieve O(nlog(n)) worst-case time complexity.
  • Aim for minimum additional space; using an in-place algorithm is ideal.
  • Heap sort is a good candidate because it offers O(nlog(n)) time with O(1) additional space.

Space and Time Complexity

Time Complexity: O(nlog(n)) Space Complexity: O(1) (in-place)

Solution

The chosen approach is Heap Sort. Heap sort works by first building a max heap from the input array. A max heap is a complete binary tree where the value in each node is greater than or equal to the values in its children. After the max heap is constructed, the largest element is at the root of the heap. Then, we repeatedly swap the root of the heap with the last element of the heap and reduce the heap size by one. We then re-heapify the root to restore the max heap property. This process continues until the heap is empty and the array is sorted in ascending order.

Key steps in the algorithm:

  • Build the max heap in-place by calling a helper function (heapify) for each non-leaf node.
  • Iteratively swap the first element (largest in the heap) with the last element and reduce the heap size.
  • Re-heapify the array from the root index to ensure the max heap property is maintained.

This approach avoids the extra space required for algorithms like merge sort and guarantees O(nlog(n)) worst-case time.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with line-by-line comments.

def heapify(nums, heap_size, root_index):
    # Initialize largest as the root index
    largest = root_index
    left_child = 2 * root_index + 1  # left child index
    right_child = 2 * root_index + 2 # right child index

    # If left child exists and is larger than the current largest, update largest
    if left_child < heap_size and nums[left_child] > nums[largest]:
        largest = left_child

    # If right child exists and is larger than the current largest, update largest
    if right_child < heap_size and nums[right_child] > nums[largest]:
        largest = right_child

    # If largest is not the root, swap the values and heapify the affected subtree
    if largest != root_index:
        nums[root_index], nums[largest] = nums[largest], nums[root_index]
        heapify(nums, heap_size, largest)

def sortArray(nums):
    n = len(nums)
    # Build a max heap by heapifying each non-leaf node (from n//2 - 1 down to 0)
    for i in range(n // 2 - 1, -1, -1):
        heapify(nums, n, i)
    
    # Extract elements one by one from the heap
    for i in range(n - 1, 0, -1):
        # Move current root to the end (swap)
        nums[0], nums[i] = nums[i], nums[0]
        # Heapify the reduced heap to maintain max heap invariant
        heapify(nums, i, 0)
    
    return nums

# Example usage:
# print(sortArray([5,2,3,1]))
← Back to All Questions