Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sort array with with first half and second half sorted [duplicate]

Tags:

c

algorithm

Possible Duplicate:
Regarding in-place merge in an array

Stumbled upon this interview question. Given an array of size n where first n/2 is sorted and the second half is sorted. Sort the entire array in place. Now what I can think of in place is somewhat like insertion sort, that'll have space complexity as O(1), but time complexity will be more than O(n). Is an O(n) in place solution possible for this problem?

like image 206
Rohit Jain Avatar asked Jun 26 '11 10:06

Rohit Jain


People also ask

How do you sort a sorted half array?

Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array. Method 1: A Simple Solution is to sort the array using built in functions (generally an implementation of quick sort).

How do you sort first half in ascending and second half in descending?

Algorithm : Sort the given array. Run a loop up to half the length of the array and print the elements of the sorted array. Run a loop from the last index of the array to the middle of the array and print the elements in reverse order.

Which sorting algorithm has two halves?

Merge Sort This sorting algorithm is based on the Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.


2 Answers

Have two (logical) pointers - lets call them x and y. x points to the 1st element of the first n/2 elements. y points to the 1st element of the second n/2 elements.

If element at y is lesser than the one at x (let's call n(y) and n(x)), then insert n(y) at x and increment x & y by 1. Else increment x by 1 and check again. Once y hits 'n', stop y and keep repeating till x == y.

E.g.

2 4 7 8 1 3 5 6
x       y

1 2 4 7 8 3 5 6
  x       y 

1 2 4 7 8 3 5 6
    x     y

1 2 3 4 7 8 5 6
      x     y

1 2 3 4 7 8 5 6
        x   y  

1 2 3 4 5 7 8 6
          x   y

1 2 3 4 5 6 7 8
            x y

1 2 3 4 5 6 7 8
              (x,y) 
like image 96
sparkymat Avatar answered Oct 22 '22 08:10

sparkymat


Normally for sorting two already sorted lists, you would use merge sort; the simplest way would be to copy one of the half arrays somewhere. That is not in-place, but works.

Swapping elements doesn't work, as it does not guarantee the maximum value of the first half of the array is less than the minimum value in the right half:

{ 3 4 4 1 2 4 }

swap i=0,j=3

{ 1 4 4 3 2 4 }

swap i=1, j=5

{ 1 2 4 3 4 4 }

Fixing this by further swapping results in an O(N^2) bubble sort.

like image 23
Pete Kirkham Avatar answered Oct 22 '22 06:10

Pete Kirkham