def insertionSort(array):

    for step in range(1, len(array)):
        key = array[step]
        j = step - 1
        
        # Compare key with each element on the left of it until an element smaller than it is found
        # For descending order, change key<array[j] to key>array[j].        
        while j >= 0 and key < (array[j]):
            array[j + 1] = array[j]
            j = j - 1
        
        # Place key at after the element just smaller than it.
        array[j + 1] = key

    result = list()
    for i in array:
        result.append(chr(i))
    output = ''
    for i in result:
        output = output+i
    return output


string = "welcome"
array = list()
for i in string:
    array.append(ord(i))
print('Sorted Array in Ascending Order:', end = '')
print(insertionSort(array))
