## Algorithm Problem: In-Place Merge Sort

The original merge sort version will take O(n) space, and O(nlogn) time.

The O(n) space is the most significant problem of this algorithm. However, there is an O(1) space version, called ‘in-place merge sort’.

## CCI题目：3-6：Stack Sort

1.逐个从st中pop元素，先pop到一个临时变量，如果pop出来的元素比临时变量小，则直接进入buffer，否则，把临时变量顶入buffer，st新pop到临时变量。

2.将buffer中的元素全部倒回st
3.重复1，2两步，直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些（在阶上没有提升），就是在st到buffer中处理的过程中，允许中途将buffer中的元素倒回一部分到st，直到临时变量找到位置，然后继续将st向buffer倒。直到st为空。

Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
//

# include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}

## LeetCode题目：Sort Colors

cur从0到j扫描，

Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with an one-pass algorithm using only constant space?

```class Solution {
public:
inline void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void sortColors(int A[], int n) {
if(n <= 1) return;
int i = 0,j = n-1;
int cur = i;
while(cur <= j) {
if(A[cur] == 0) {
if(cur > i) {
swap(A[i++],A[cur]);
} else {
++cur;
++i;
}
} else if (A[cur] == 2) {
if(cur < j)
swap(A[j--],A[cur]);
else
return;
} else
++cur;
}
}
};
```

## LeetCode题目：Merge Sorted Array

Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int last = m + n - 1;
int lasta = m - 1;
int lastb = n - 1;
//select largest to right position
while(lasta >= 0 && lastb >= 0) {
A[last--] = (A[lasta] >= B[lastb] ? A[lasta--] : B[lastb--]);
}
//copy remain numbers in B to A
for(int i = 0 ; i <= lastb; ++i)
A[i] = B[i];
}
};
```

Code rewrite at 2012-12-22

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int curi = m + n - 1;
int ia = m - 1;
int ib = n - 1;
while(ia >= 0 && ib >= 0) {
if(A[ia] >= B[ib]) {
A[curi--] = A[ia--];
} else {
A[curi--] = B[ib--];
}
}
while (ib >= 0) {
A[curi--] = B[ib--];
}
}
};
```

Code rewrite at 2012-12-22, The simplest code

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ia = m - 1, ib = n - 1, icur = m + n - 1;
while(ia >= 0 && ib >= 0) {
A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
}
while(ib >= 0) {
A[icur--] = B[ib--];
}
}
};
```

## iOS开发中对NSArray或者NSMutableArray中的内容排序

``` NSMutableArray *feedsBuffer; //初始化buffer以及填充数据 //....... //排序只需要两句话:已针对数组内对象的publishTime属性(NSDate)排序为例： NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc] initWithKey:@"publishTime" ascending:NO]; [feedsBuffer sortUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]]; ```

``` NSArray *sortedArray = [feedsBuffer sortedArrayUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]]; ```

``` [feedsBuffer sortUsingComparator:^NSComparisonResult(id obj1, id obj2) { //返回三者其一:NSOrderedAscending, NSOrderedSame, NSOrderedDescending return NSOrderedSame; }]; ```