I tried to program Interiewstreet's Insertion sort challenge Link for the challenge in Python and here is my code shown below.
The program runs fine for a limit(which I'm not sure of) of input elements, but returns a false output for inputs of larger sizes. Can anyone guide me what am I doing wrong?
# This program tries to identify number of times swapping is done to sort the input array """ =>Get input values and print them =>Get number of test cases and get inputs for those test cases =>Complete Insertion sort routine =>Add a variable to count the swapping's """ def sort_swap_times(nums): """ This function takes a list of elements and then returns the number of times swapping was necessary to complete the sorting """ times_swapped = 0L # perform the insertion sort routine for j in range(1, len(nums)): key = nums[j] i = j - 1 while i >= 0 and nums[i] > key: # perform swap and update the tracker nums[i + 1] = nums[i] times_swapped += 1 i = i - 1 # place the key value in the position identified nums[i + 1] = key return times_swapped # get the upper limit. limit = int(raw_input()) swap_count =  # get the length and elements. for i in range(limit): length = int(raw_input()) elements_str = raw_input() # returns a list of strings # convert the given elements from str to int elements_int = map(int, elements_str.split()) # pass integer elements list to perform the sorting # get the number of times swapping was needed and append the return value to swap_count list swap_count.append(sort_swap_times(elements_int)) # print the swap counts for each input array for x in swap_count: print x