How To Sort An Array With N Elements In Which K Elements Are Out Of Place In O(n + K Log K)?

I was asked this in an interview today, and am starting to believe it is not solvable. Given a sorted array of size n, select k elements in the array, and reshuffle them back into

Solution 1:

Note: This is a conceptual solution. It is coded in Python, but because of the way Python implements List, does not actually run in the required complexity. See soyuzzzz's answer to see an actual solution in Python in the complexity requirement.

Accepted @soyuzzzz's answer over this one.

Original answer (works, but the complexity is only correct assuming Linked list implementation for Python's List, which is not the case):

This sorts a nk-unsorted array in O(n + klogk), assuming the array should be ascending.

1. Find elements which are not sorted by traversing the array.
2. If such an element was found (it is larger then the following one), then either it or the following one are out of order (or both).
3. Keep both of them aside, and remove them from the array
4. continue traversing on the newly obtained array (after removal), form the index which comes before the found element.
5. This will put aside 2k elements in O(n) time.
6. Sort 2k elements O(klogk)
7. Merge two sorted lists which have total n elements, O(n)
8. Total O(n + klogk)

Code:

def merge_sorted_lists(la, lb):
    if la is None or la == []:
        return lb
    if lb is None or lb == []:
        return la
    a_ind = b_ind = 0
    a_len = len(la)
    b_len = len(lb)

    merged = []
    while a_ind < a_len and b_ind < b_len:
        a_value = la[a_ind]
        b_value = lb[b_ind]

        if a_value < b_value:
            merged.append(la[a_ind])
            a_ind += 1
        else:
            merged.append(lb[b_ind])
            b_ind += 1

    # get the leftovers into merged
    while a_ind < a_len:
        merged.append(la[a_ind])
        a_ind += 1
    while b_ind < b_len:
        merged.append(lb[b_ind])
        b_ind += 1

    return merged

and

def sort_nk_unsorted_list(nk_unsorted_list):
    working_copy = nk_unsorted_list.copy()  # just for ease of testing

    requires_resorting = []

    current_list_length = len(working_copy)
    i = 0
    while i < current_list_length - 1 and 1 < current_list_length:
        if i == -1:
            i = 0

        first = working_copy[i]
        second = working_copy[i + 1]

        if second < first:
            requires_resorting.append(first)
            requires_resorting.append(second)

            del working_copy[i + 1]
            del working_copy[i]
            i -= 2
            current_list_length -= 2
        i += 1

    sorted_2k_elements = sorted(requires_resorting)
    sorted_nk_list = merge_sorted_lists(sorted_2k_elements, working_copy)
    return sorted_nk_list

Solution 2:

Even though @Gulzar's solution is correct, it doesn't actually give us O(n + k * log k). The problem is in the sort_nk_unsorted_list function. Unfortunately, deleting an arbitrary item from a Python list is not constant time. It's actually O(n). That gives the overall algorithm a complexity of O(n + nk + k * log k)

What we can do to address this is use a different data structure. If you use a doubly-linked list, removing an item from that list is actually O(1). Unfortunately, Python does not come with one by default.

Here's my solution that achieves O(n + k * log k).

The entry-point function to solve the problem:

def sort(my_list):
    in_order, out_of_order = separate_in_order_from_out_of_order(my_list)

    out_of_order.sort()

    return merge(in_order, out_of_order)

The function that separates the in-order elements from the out-of-order elements:

def separate_in_order_from_out_of_order(my_list):
    list_dll = DoublyLinkedList.from_list(my_list)
    out_of_order = []
    
    current = list_dll.head

    while current.next is not None:
        if current.value > current.next.value:
            out_of_order.append(current.value)
            out_of_order.append(current.next.value)

            previous = current.prev

            current.next.remove()
            current.remove()

            current = previous
        else:
            current = current.next

    in_order = list_dll.to_list()

    return in_order, out_of_order

The function to merge the two separated lists:

def merge(first, second):
    """
    Merges two [sorted] lists into a sorted list.

    Runtime complexity: O(n)
    Space complexity: O(n)
    """
    i, j = 0, 0

    result = []
    
    while i < len(first) and j < len(second):
        if first[i] < second[j]:
            result.append(first[i])
            i += 1            
        else:
            result.append(second[j])
            j += 1            

    result.extend(first[i:len(first)])
    result.extend(second[j:len(second)])

    return result

And last, this is the DoublyLinkedList implementation (I used a sentinel node to make things easier):

class DoublyLinkedNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

    def remove(self):
        if self.prev:
            self.prev.next = self.next

        if self.next:
            self.next.prev = self.prev
        

class DoublyLinkedList:
    def __init__(self, head):
        self.head = head

    @staticmethod
    def from_list(lst):
        sentinel = DoublyLinkedNode(-math.inf)
        previous = sentinel

        for item in lst:
            node = DoublyLinkedNode(item)
            node.prev = previous
            previous.next = node

            previous = node
        
        return DoublyLinkedList(sentinel)

    def to_list(self):
        result = []
        current = self.head.next

        while current is not None:
            result.append(current.value)
            current = current.next

        return result

And these are the unit tests I used to validate the code:

import unittest


class TestSort(unittest.TestCase):
    def test_sort(self):
        test_cases = [
            # ( input, expected result)
            ([1, 2, 3, 4, 10, 5, 6], [1, 2, 3, 4, 5, 6, 10]),
            
            ([1, 2, 5, 4, 10, 6, 0], [0, 1, 2, 4, 5, 6, 10]),

            ([1], [1]),

            ([1, 3, 2], [1, 2, 3]),
            ([], [])
        ]

        for (test_input, expected) in test_cases:
            result = sort(test_input)
        
            self.assertEqual(expected, result)