#6.Write a test program to implement Divide and Conquer Strategy. Eg: Quick sort algorithm  for sorting list of integers in ascending order.


def quick_sort(arr):
    # Base case: array with 0 or 1 element is already sorted
    if len(arr) <= 1:
        return arr
    
    
    pivot = arr[-1]
    left = []  # Elements less than pivot
    right = []  # Elements greater than pivot
    equal = []  # Elements equal to pivot

    # Partition the array based on pivot
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            equal.append(num)
    
    
    return quick_sort(left) + equal + quick_sort(right)

# Test program
if __name__ == "__main__":
    arr = [10, 7, 8, 9, 1, 5]
    print("Original array:", arr)
    sorted_arr = quick_sort(arr)
    print("Sorted array:", sorted_arr)